У вас есть две строки \(a\) и \(b\) равной чётной длины \(n\), состоящие из символов 0 и 1.
Пошёл финальный раунд. Чтобы наконец сделать Вселенную идеально сбалансированной, вам нужно сделать строки \(a\) и \(b\) равными.
За один шаг вы можете выбрать любой префикс \(a\) чётной длины и перевернуть его. Формально, если \(a = a_1 a_2 \ldots a_n\), вы можете выбрать любое положительное чётное число \(p \le n\) и сделать \(a\) равной \(a_p a_{p-1} \ldots a_1 a_{p+1} a_{p+2} \ldots a_n\).
Найдите способ сделать строки \(a\) и \(b\) равными, используя не более \(n + 1\) переворотов такого рода, или определите, что такого способа не существует. Минимизировать число переворотов не нужно.
Выходные данные
Для каждого теста, если невозможно сделать \(a\) и \(b\) равными, используя не более \(n + 1\) переворотов, выведите число \(-1\).
В противном случае выведите целое число \(k\) (\(0 \le k \le n + 1\)) — число переворотов в вашей последовательности шагов, и \(k\) чётных чисел \(p_1, p_2, \ldots, p_k\) (\(2 \le p_i \le n\); \(p_i \bmod 2 = 0\)) — длины префиксов \(a\), которые нужно перевернуть, в хронологическом порядке.
Обратите внимание, что \(k\) минимизировать не нужно. Если есть несколько решений, выведите любое из них.
Примечание
В первом тесте строка \(a\) меняется следующим образом:
- после первого переворота: 1000101011;
- после второго переворота: 0001101011;
- после третьего переворота: 1101011000.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0100011011
1101011000
10101010
10101010
0011
1001
100011
110010
|
3
6 4 10
0
-1
7
2 6 2 6 2 2 6
|