Двоичная строка — это такая строка, каждый символ которой — либо 0, либо 1. Назовем две двоичные строки \(a\) и \(b\) одинаковой длины похожими, если хотя бы в одной позиции их символы совпадают (существует такое число \(i\), что \(a_i = b_i\)). Например:
- 10010 и 01111 похожи (у них один и тот же символ в позиции \(4\));
- 10010 и 11111 похожи;
- 111 и 111 похожи;
- 0110 и 1001 не являются похожими.
Вам дано целое число \(n\) и двоичная строка \(s\), состоящая из \(2n-1\) символов. Обозначим за \(s[l..r]\) непрерывную подстроку \(s\), начиная с \(l\)-го символа и заканчивая \(r\)-м символом (иными словами, \(s[l..r] = s_l s_{l + 1} s_{l + 2} \dots s_r\)).
Постройте двоичную строку \(w\) длины \(n\), похожую на все строки из этого списка: \(s[1..n]\), \(s[2..n+1]\), \(s[3..n+2]\), ..., \(s[n..2n-1]\).
Выходные данные
Для каждого набора входных данных выведите удовлетворяющую условию двоичную строку \(w\) длины \(n\). Если существует несколько таких строк — выведите любую из них. Можно показать, что хотя бы одна такая строка \(w\) всегда существует.
Примечание
Объяснение примера из условия (совпадающие символы в одинаковых позициях выделены жирным):
Первый набор входных данных:
- \(\mathbf{1}\) похожа на \(s[1..1] = \mathbf{1}\).
Второй набор входных данных:
- \(\mathbf{000}\) похожа на \(s[1..3] = \mathbf{000}\);
- \(\mathbf{000}\) похожа на \(s[2..4] = \mathbf{000}\);
- \(\mathbf{000}\) похожа на \(s[3..5] = \mathbf{000}\).
Третий набор входных данных:
- \(\mathbf{1}0\mathbf{10}\) похожа на \(s[1..4] = \mathbf{1}1\mathbf{10}\);
- \(\mathbf{1}01\mathbf{0}\) похожа на \(s[2..5] = \mathbf{1}10\mathbf{0}\);
- \(\mathbf{10}1\mathbf{0}\) похожа на \(s[3..6] = \mathbf{10}0\mathbf{0}\);
- \(1\mathbf{0}1\mathbf{0}\) похожа на \(s[4..7] = 0\mathbf{0}0\mathbf{0}\).
Четвертый набор входных данных:
- \(0\mathbf{0}\) похожа на \(s[1..2] = 1\mathbf{0}\);
- \(\mathbf{0}0\) похожа на \(s[2..3] = \mathbf{0}1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
1
3
00000
4
1110000
2
101
|
1
000
1010
00
|