У Циншань есть строка \(s\), которая содержит только \(\texttt{0}\) и \(\texttt{1}\).
Строка \(a\) длины \(k\) является хорошей тогда и только тогда, когда
- \(a_i \ne a_{k-i+1}\) для всех \(i=1,2,\ldots,k\).
Для участников Div. 2: обратите внимание, что это условие отличается от условия в задаче B.
Например, \(\texttt{10}\), \(\texttt{1010}\), \(\texttt{111000}\) — хорошие строки, а \(\texttt{11}\), \(\texttt{101}\), \(\texttt{001}\), \(\texttt{001100}\) — плохие.
Циншань хочет сделать \(s\) хорошей. Для этого она может проделать следующую операцию не более \(300\) раз (возможно, ноль):
- вставить \(\texttt{01}\) в любое место строки \(s\) (получив новую строку \(s\)).
Скажите, возможно ли сделать \(s\) хорошей. Если это возможно, то приведите последовательность операций, которая делает строку \(s\) хорошей.
Выходные данные
Для каждого набора входных данных, если невозможно сделать \(s\) хорошей, выведите \(-1\).
В противном случае в первой строке выведите \(p\) (\(0 \le p \le 300\)) — количество операций.
Затем выведите \(p\) целых чисел во второй строке. Целое число \(i\) должно быть индексом \(x_i\) (\(0 \le x_i \le n+2i-2\)) — позицией, в которую необходимо вставить \(\texttt{01}\) в текущем \(s\). Если \(x_i=0\), то \(\texttt{01}\) вставляется в начало \(s\). В противном случае, \(\texttt{01}\) вставляется сразу после \(x_i\)-го символа \(s\).
Можно показать, что при данных ограничениях, если ответ существует, то всегда найдется ответ, требующий не более \(300\) операций.
Примечание
В первом наборе входных данных можно выполнить ноль операций и получить \(s=\texttt{01}\), что является хорошей строкой.
Другим правильным решением является выполнение одной операции: (вставленная \(\texttt{01}\) подчеркнута)
- \(\texttt{0}\underline{\texttt{01}}\texttt{1}\)
получаем \(s = \texttt{0011}\), что является хорошей строкой.
Во втором и третьем наборах входных данных сделать \(s\) хорошей невозможно.
В четвертом наборе входных данных можно выполнить две операции:
- \(\texttt{001110}\underline{\texttt{01}}\)
- \(\texttt{0011100}\underline{\texttt{01}}\texttt{1}\)
и получить \(s = \texttt{0011100011}\), что является хорошей строкой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
|
0
-1
-1
2
6 7
1
10
-1
|