У Эврула есть бинарная строка \(s\) длины \(2n\). Бинарная строка — это строка, состоящая только из символов \(0\) и \(1\). Он хочет разбить \(s\) на две непересекающиеся одинаковые подпоследовательности. Для этого ему нужна ваша помощь.
Вы можете выполнить следующую операцию один раз.
- Выберите любую подпоследовательность (возможно пустую) символов \(s\) и циклически сдвиньте ее направо на одну позицию.
Другими словами, выберите последовательность индексов \(b_1, b_2, \ldots, b_m\), где \(1 \le b_1 < b_2 < \ldots < b_m \le 2n\). После этого одновременно присвойте \(\)s_{b_1} := s_{b_m},\(\) \(\)s_{b_2} := s_{b_1},\(\) \(\)\ldots,\(\) \(\)s_{b_m} := s_{b_{m-1}}.\(\)
Можете ли вы разбить \(s\) на две непересекающиеся одинаковые подпоследовательности после того, как выполните указанную операцию ровно один раз?
Разбиением \(s\) на две непересекающиеся одинаковые подпоследовательности \(s^p\) и \(s^q\) называются два возрастающих массива индексов \(p_1, p_2, \ldots, p_n\) и \(q_1, q_2, \ldots, q_n\) такие, что каждое целое число от \(1\) до \(2n\) встречается \(p\) и \(q\) ровно один раз, при этом \(s^p = s_{p_1} s_{p_2} \ldots s_{p_n}\), \(s^q = s_{q_1} s_{q_2} \ldots s_{q_n}\), и \(s^p = s^q\).
Если невозможно выполнить операцию и разбиение, выведите \(-1\). Если можно выполнить операцию и разбить \(s\) на две непересекающиеся подпоследовательности \(s^p\) и \(s^q\) так, чтобы \(s^p = s^q\), выведите индексы подпоследовательности \(b\) и индексы \(s^p\), т. е. значения \(p_1, p_2, \ldots, p_n\).
Выходные данные
Для каждого набора входных данных следуйте следующему формату.
Если решения не существует, выведите \(-1\).
Иначе:
- В первой строке выведите целое число \(m\) (\(0 \leq m \leq 2n\)) и затем \(m\) различных индексов в возрастающем порядке \(b_1\), \(b_2\), ..., \(b_m\).
- Во второй строке выведите \(n\) различных индексов в возрастающем порядке \(p_1\), \(p_2\), ..., \(p_n\).
Если существуют несколько решений, выведите любое из них.
Примечание
В первом примере \(b\) пустая, поэтому строка \(s\) не меняется. Выберем \(s^p = s_1 s_2 = \mathtt{10}\), тогда \(s^q = s_3s_4 = \mathtt{10}\).
Во втором примере \(b=[3,5]\). Изначально \(s_3=\mathtt{0}\), и \(s_5=\mathtt{1}\). После выполнения операции мы одновременно присваиваем \(s_3=\mathtt{1}\) и \(s_5=\mathtt{0}\).
Поэтому \(s\) становится 101000 после выполнения операции.
Возьмем символы на позициях \([1,2,5]\) в \(s^p\), получим \(s_1=\mathtt{100}\). Символы на позициях \([3,4,6]\) будут в \(s^q\), получим \(s^q=100\). Это решение, потому что \(s^p=s^q\).
В четвертом примере можно показать, что невозможно выполнить разбиение строки после любой операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1010
3
100010
2
1111
2
1110
|
0
1 2
2 3 5
1 2 5
3 2 3 4
1 4
-1
|