В \(2022\) году Миша нашёл два числа \(a\) и \(b\) длины \(n\), записанных в двоичной системе счисления (то есть для их записи были использованы только цифры \(0\) и \(1\)), оба из которых могут содержать ведущие нули. Чтобы их не забыть, он решил создать число \(d\) следующим образом:
- сначала он получит число \(c\) в результате поразрядного сложения чисел \(a\) и \(b\) без переносов, из-за чего \(c\) может содержать одну или более цифр \(2\). Например, в результате поразрядного сложения чисел \(0110\) и \(1101\) получится число \(1211\), a в результате поразрядного сложения чисел \(011000\) и \(011000\) получится \(022000\).
- после этого (чтобы запоминать меньше цифр) Миша заменит последовательные вхождения одной и той же цифры в \(c\) на одну цифру, тем самым получив число \(d\). В вышеописанном примере число \(1211\) Миша заменит на \(121\), а число \(022000\) — на \(020\) (таким образом, в числе \(d\) не может быть двух одинаковых цифр подряд).
К сожалению, Миша потерял число
\(a\) до того, как вычислил
\(d\). Чтобы обрадовать его, Вы решили найти
любое число
\(a\) длины
\(n\) такое, что
\(d\) будет
максимально возможным как число.
Максимально возможным как число означает, что \(102 > 21\), \(012 < 101\), \(021 = 21\) и тому подобное.
Выходные данные
Для каждого набора входных данных, выведите одно двоичное число \(a\) длины \(n\). Обратите внимание, что числа \(a\) и \(b\) могут содержать ведущие нули, но их длина должна быть равна \(n\).
Примечание
В первом наборе входных данных, \(b = 0\) и при выборе \(a = 1\) получится \(d = 1\).
Во втором наборе, \(b = 011\).
- Если выбрать \(a = 000\), \(c\) будет равно \(011\), и \(d = 01\).
- Если выбрать \(a = 111\), \(c\) будет равно \(122\), и \(d = 12\).
- Если выбрать \(a = 010\), получится \(d = 021\).
- Если выбрать \(a = 110\), получится \(d = 121\).
Можно показать, что ответ
\(a = 110\) является верным, и
\(d = 121\) является максимальным.
В третьем наборе, \(b = 110\). При выборе \(a = 100\) получится \(d = 210\). Это максимальное возможное \(d\) в данном случае.
В четвертом наборе, \(b = 111000\). При выборе \(a = 101101\) получится \(d = 212101\). Это максимальное возможное \(d\) в данном случае.
В пятом наборе, \(b = 001011\). При выборе \(a = 101110\) получится \(d = 102121\). Это максимальное возможное \(d\) в данном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
0
3
011
3
110
6
111000
6
001011
|
1
110
100
101101
101110
|