Дана бинарная строка \(s\) длины \(2n\), каждый элемент которой равняется \(\mathtt{0}\) или \(\mathtt{1}\). Вы можете выполнять следующую операцию:
- Выбрать правильную скобочную последовательность\(^\dagger\) \(b\) длины \(2n\).
- Пройти по всем индексам \(i\) от \(1\) до \(2n\) по порядку. Если \(b_i\) — открывающая скобка, то обозначим за \(p_i\) минимальный индекс такой, что \(b[i,p_i]\) — правильная скобочная последовательность. Тогда к подотрезку с \(i\) по \(p_i\) из бинарной строки \(s\) применяется операция инвертирования\(^\ddagger\). Заметим, что поскольку правильная скобочная последовательность длины \(2n\) будет иметь \(n\) открывающих скобок, то мы выполним \(n\) операций инвертирования подотрезка над \(s\).
Ваша задача — найти последовательность из не более чем \(10\) операций, изменяющую все элементы \(s\) на \(\mathtt{0}\), или определить, что это невозможно. Заметим, что минимизировать количество операций не обязательно.
При заданных ограничениях можно доказать, что если существует способ изменить все элементы \(s\) на \(\mathtt{0}\), то существует способ, требующий не более \(10\) операций.
\(^\dagger\) Скобочная последовательность называется правильной, если ее можно превратить в корректное математическое выражение, добавив символы \(+\) и \(1\). Например, последовательности «(()()», «()» и «(()(())» являются правильными, а «)(», «(()» и «(())(» — не являются.
\(^\ddagger\) Если мы выполним операцию инвертирования для подотрезка с \(l\) по \(r\) бинарной строки \(s\), то мы инвертируем все значения \(s_i\) такие, что \(l \leq i \leq r\). Если \(s_i\) инвертируется, то мы присваиваем \(s_i := \mathtt{0}\), если изначально было \(s_i = \mathtt{1}\), и наоборот. Например, если \(s=\mathtt{1000101}\) и мы выполняем операцию инвертирования подотрезка с \(3\) по \(5\), то \(s\) изменится на \(s=\mathtt{1011001}\).
Выходные данные
Для каждого набора входных данных выведите в единственной строке \(-1\), если невозможно изменить все элементы \(s\) на \(\mathtt{0}\).
В противном случае выведите одно целое число \(k\) (\(0 \le k \le 10\)), равняющееся количеству операций, необходимому для изменения всех элементов \(s\) на \(\mathtt{0}\). Затем в следующих \(k\) строках выведите правильные скобочные последовательности длины \(2n\), представляющие собой операции, необходимые для изменения всех элементов \(s\) на \(0\).
Если существует несколько способов изменить все элементы \(s\) на \(\mathtt{0}\), требующих не более \(10\) операций, то можно вывести любой из них.
Примечание
В первом наборе входных данных можно показать, что невозможно изменить все элементы \(s\) на \(\mathtt{0}\).
Во втором наборе входных данных первая операция с использованием последовательности скобок \(b = \mathtt{()()}\) преобразует двоичную строку \(s=\mathtt{0000}\) в \(s=\mathtt{1111}\). Затем вторая операция с использованием той же последовательности скобок \(b = \mathtt{()()}\) преобразует двоичную строку \(s=\mathtt{1111}\) обратно в \(s=\mathtt{0000}\). Заметим, что поскольку все элементы \(s\) изначально уже равнялись \(\mathtt{0}\), то использование \(0\) операций также является правильным ответом.
В третьем наборе входных данных одна операция с использованием последовательности скобок \(b = \mathtt{(())()}\) изменит все элементы \(s\) на \(\mathtt{0}\). Операция будет происходить следующим образом:
- \(b_1\) — открывающая скобка, а \(p_1 = 4\), так как \(b[1,4]=\mathtt{(())}\) — правильная скобочная последовательность. Следовательно, выполнив операцию инвертирования подотрезка с \(1\) по \(4\) на бинарной строке \(s = \mathtt{100111}\), мы получим \(s = \mathtt{011011}\).
- \(b_2\) является открывающей скобкой, а \(p_2 = 3\), так как \(b[2,3]=\mathtt{()}\) является правильной скобочной последовательностью. Следовательно, выполнив операцию инвертирования подотрезка с \(2\) по \(3\) на бинарной строке \(s = \mathtt{011011}\), мы получим \(s = \mathtt{000011}\).
- \(b_3\) не является открывающей скобкой, поэтому на этом шаге операция инвертирования не выполняется.
- \(b_4\) не является открывающей скобкой, поэтому на этом шаге операция инвертирования не выполняется.
- \(b_5\) является открывающей скобкой, а \(p_5 = 6\), так как \(b[5,6]=\mathtt{()}\) является правильной скобочной последовательностью. Следовательно, выполнив операцию инвертирования подотрезка с \(5\) по \(6\) для бинарной строки \(s = \mathtt{000011}\), мы получим \(s = \mathtt{000000}\).
- \(b_6\) не является открывающей скобкой, поэтому на этом шаге операция инвертирования не выполняется.
В четвертом наборе входных данных первая операция с использованием скобочной последовательности \(b = \mathtt{(((())))}\) преобразует бинарную строку \(s = \mathtt{01011100}\) в \(s = \mathtt{11111001}\). Затем, вторая операция с использованием скобочной последовательности \(b = \mathtt{()()(())}\) преобразует бинарную строку \(s = \mathtt{11111001}\) в \(s=\mathtt{00000000}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
01
2
0000
3
100111
4
01011100
|
-1
2
()()
()()
1
(())()
2
(((())))
()()(())
|