Вам дана бинарная строка \(s\) длины \(n\) (строка - состоящая только из \(0\) и \(1\)). Число \(x\) является хорошим, если существует такая бинарная строка \(l\) длины \(n\), содержащая \(x\) единиц, что если каждый символ \(s_i\) заменить на \(s_i \oplus l_i\) (где \(\oplus\) обозначает операцию Побитового исключающего ИЛИ) то строка \(s\) станет палиндромом.
Нужно вывести бинарную строку \(t\) длины \(n+1\), где \(t_i\) (\(0 \leq i \leq n\)) равно \(1\) если число \(i\) хорошее, и \(0\) иначе.
Палиндром — это строка, которая читается одинаково как слева направо, так и справа налево. Например, строки 01010, 1111, 0110 — палиндромы.
Выходные данные
Для каждого набора входных данных выведите одну строку \(t\) длины \(n+1\) - ответ на задачу.
Примечание
Рассмотрим первый пример.
- \(t_2 = 1\) так как можно выбрать \(l = \) 010100 тогда строка \(s\) станет равна 111111, что является палиндромом.
- \(t_4 = 1\) так как можно выбрать \(l = \) 101011.
- Можно показать, что для всех остальных \(i\) ответа не существует, поэтому остальные символы равны \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
6
101011
5
00000
9
100100011
3
100
1
1
|
0010100
111111
0011111100
0110
11
|