Background

Original problem link: https://oier.team/problems/X2C。

Along the one-sided endless echoing melody, it flows through the streets before my eyes, together with a love that has come to an end, fading farther and farther away.
That ideal blueprint that cannot be conveyed grows more and more twisted; the silent resistance awakens at this very moment, and the impulse also arrives late at this very moment.
Broken cries and beautiful dreams; the ideal is left with only a decorative facade.
Even if the city is willing to be drowned in noise and clamor,
I will keep singing loudly and give up everything that controls me.
So I only wish that silence can echo once again.

No need to fear; dawn has already arrived.

Problem 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 need to choose an index $p$ such that $p$ is $1$ or $n$ or $a_{p-1}\neq a_{p+1}$, and then flip $a_p$ (that is, change $0$ to $1$, and change $1$ to $0$).

Please make the sequence $a$ become all $0$'s or all $1$'s within $r$ operations. You do not need to minimize the number of operations. If it cannot be done, you need to report that there is no solution.

The testdata guarantees that $\bm{r = 2 \times 10^6}$ or $\bm{10^6}$. For details, please see the Constraints section.

Input Format

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

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

Output Format

If it is impossible to make the sequence $a$ become all $0$'s or all $1$'s within $r$ operations, output one line with one integer $-1$.

If there exists a constructive solution, output two lines:

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

4 1000000
0 0 1 0

3
2 4 1

5 1000000
1 1 1 1 1

0

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

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

Hint

[Sample Explanation #1]

The sequence $a$ after each operation is, respectively:

• $[0,1,1,0]$；
• $[0,1,1,1]$；
• $[1,1,1,1]$。

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

[Constraints]

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

This problem uses bundled tests.

• 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$.

Translated by ChatGPT 5