На столе в ряд выложены \(n\) кубиков, каждый из которых покрашен в черный или белый цвет. Кубики пронумерованы слева направо, начиная с единицы.
Вы можете ноль или более раз применить к последовательности кубиков следующую операцию: выбрать два соседних кубика и инвертировать их цвета (заменить белый на чёрный, и наоборот).
Определите такую последовательность операций, что после их применения все кубики станут либо полностью белыми, либо полностью чёрными. Вам не нужно минимизировать количество операций, но их количество не должно превосходить \(3 \cdot n\). Если невозможно сделать все кубики одноцветными, сообщите об этом.
Выходные данные
Если невозможно сделать все кубики одноцветными с помощью описанных операций, выведите \(-1\).
В противном случае, в первую строку выведите целое число \(k\) (\(0 \le k \le 3 \cdot n\)) — количество операций, которые нужно произвести. Во второй строке выведите \(k\) целых чисел \(p_1, p_2, \dots, p_k\) \((1 \le p_j \le n - 1)\), где \(p_j\) равно позиции левого из двух соседних кубиков, у которых нужно инвертировать цвета во время \(j\)-й операции.
Если ответов несколько, разрешается вывести любой из них.
Примечание
В первом примере можно сделать все кубики чёрными, например, за \(3\) операции. Сначала можно инвертировать цвета кубиков в позициях \(6\) и \(7\). После этого последовательность цветов кубиков будет выглядеть как «BWWWWBBB». Затем можно инвертировать цвета кубиков в позициях \(2\) и \(3\). После этого последовательность цветов кубиков будет выглядеть как «BBBWWBBB». В ходе третьей операции нужно инвертировать цвета кубиков в позициях \(4\) и \(5\). После этого все кубики станут чёрного цвета.
Во втором примере невозможно сделать все кубики одноцветными.
В третьем примере все кубики изначально имеют белый цвет, поэтому можно не использовать операции инвертирования цветов.
В четвертом примере можно сделать все кубики белыми за две операции. Сначала нужно инвертировать цвета кубиков \(2\) и \(3\) (последовательность цветов после этого будет выглядеть как «BBW»), а затем инвертировать цвета кубиков \(1\) и \(2\) (после этого все кубики станут белого цвета).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
BWWWWWWB
|
3
6 2 4
|
|
2
|
4
BWBB
|
-1
|
|
3
|
5
WWWWW
|
0
|
|
4
|
3
BWB
|
2
2 1
|