Description

Little $\mathrm{S}$ has $n$ crystals. Each crystal has an attribute $d_i$, which is the value of this crystal.

One day, Little $\mathrm{A}$ came to Little $\mathrm{S}$'s home and asked Little $\mathrm{S}$ to arrange the crystals into a sequence, and destroy all crystals whose value is $w$.

However, due to the special property of this sequence, each destruction must satisfy:

• The crystal's position in the sequence must be a power of $2$. That is, you can only destroy crystals at position $2^x$, where $0 \leq x \leq \log_2 y$ and $x$ is an integer, and $y$ is the current number of crystals in the sequence.

After destroying one crystal, all crystals after it move forward by one position.

For example, for the value sequence $6\ 10\ 4\ 7\ 8$, you can only destroy crystals at positions $1,2,4$.

If you destroy the crystal at position $2$, the sequence becomes $6\ 4\ 7\ 8$.

To save time, Little $\mathrm{S}$ wants to know the minimum number of destructions needed to destroy all crystals with value $w$, and what the initial position of the destroyed crystal is for the $i$-th destruction.

This problem uses Special Judge. If there are multiple answers, you may output any one of them.

Input Format

The first line contains two integers $n,w$.

The second line contains $n$ positive integers $d_i$.

Output Format

The first line contains an integer $m$, meaning the minimum number of destructions needed to destroy all crystals with value $w$.

The next line contains $m$ numbers. The $i$-th number indicates the initial position of the crystal destroyed in the $i$-th destruction, separated by spaces.

5 4
1 4 2 4 5

2
4 2

5 2
1 2 2 2 2

4
2 3 4 5

5 8
6 10 4 7 8

2
4 5

Hint

Sample Explanation

Sample $1$:

First destroy the later $4$, whose initial position is $4$. The value sequence becomes: $1\ 4\ 2\ 5$.

Then destroy the earlier $4$, whose initial position is $2$.

The total number of destructions is $2$.

Sample $2$:

First destroy the first $2$, whose initial position is $2$, and the sequence becomes: $1\ 2\ 2\ 2$.

Then destroy the remaining first $2$, whose initial position is $3$, and the sequence becomes: $1\ 2\ 2$.

Then destroy the first $2$, whose initial position is $4$, and the sequence becomes: $1\ 2$.

Then destroy the first $2$, whose initial position is $5$.

The total number of destructions is $4$.

Constraints and Notes

For $15\%$ of the testdata, $n \leq 5$.

For $25\%$ of the testdata, $n \leq 20$.

For $30\%$ of the testdata, $n \leq 1000$.

For $35\%$ of the testdata, $n \leq 10000$.

For $50\%$ of the testdata, $n \leq 3 \times 10^5$.

For $80\%$ of the testdata, $n \leq 10^6$.

For $100\%$ of the testdata, $1 \leq n \leq 3 \times 10^6, 1 \leq d_i \leq 40000$. It is guaranteed that the number of $w$ is no more than $1.5 \times 10^6$.

The shattered crystals sparkle under the sunlight...

Translated by ChatGPT 5