Background

The melody resonates endlessly along one side, flowing through the streets before my eyes, accompanied by a fading love that drifts further and further away.

The unattainable ideal composition gradually twists; the silent resistance awakens at this moment, and the impulse arrives late as well.

Fragmented cries and beautiful dreams; the ideal is left with nothing but a decorative facade.

Even if the city is happy to be drowned in noise and clamor,

I will continue to sing loudly, abandoning everything that controls me.

So I only wish for that tranquility to resonate once more.

Fear not, for the dawn has already arrived.

Description

Given a $01$ sequence $a_1, \ldots, a_n$ of length $n$ and a positive integer $r$.

You can perform operations on the sequence $a$. In each operation, you must choose an index $p$ such that $p=1$, $p=n$, or $a_{p-1} \neq a_{p+1}$, and then flip $a_p$ (i.e., change $0$ to $1$ or $1$ to $0$).

Your task is to transform the sequence $a$ into all $0$s or all $1$s within $r$ operations. You do not need to minimize the number of operations. If it is impossible, you must report that there is no solution.

The data guarantees that $\boldsymbol{r = 2 \times 10^6}$ or $\boldsymbol{10^6}$; please refer to the "Constraints" section for specific details.

Input

The first line contains two positive integers $n$ and $r$.

The second line contains $n$ integers $a_1, \ldots, a_n$.

Output

If it is impossible to transform the sequence $a$ into all $0$s or all $1$s within $r$ operations, output a single integer $-1$.

If a construction exists, output two lines:

• The first line contains a non-negative integer $m$, representing the number of operations; you must ensure $m \le r$, and you do not need to minimize $\boldsymbol m$;
• The second line contains $m$ positive integers, representing the index $p$ of each operation in sequence.

Examples

Input 1

4 1000000
0 0 1 0

Output 1

3
2 4 1

Note 1

The sequence $a$ after each operation is:

• $[0,1,1,0]$;
• $[0,1,1,1]$;
• $[1,1,1,1]$.

At this point, all elements in the sequence $a$ are the same.

Input 2

5 1000000
1 1 1 1 1

Output 2

0

Input 3

10 1000000
0 1 0 0 1 1 0 0 1 0

Output 3

18
1 2 10 1 9 4 10 4 7 4 7 3 7 8 9 2 10 1

Constraints

For all test data, $2 \le n \le 2 \times 10^3$, $a_i \in \{0, 1\}$, $r = 2 \times 10^6$ or $10^6$.

This problem uses bundled testing.

• Subtask 1 (20 points): $n \le 10$, $r = 2 \times 10^6$.
• Subtask 2 (30 points): $r = 2 \times 10^6$.
• Subtask 3 (50 points): $r = 10^6$.