Как-то раз Ам Ням нашёл нитку с надетыми на неё n камешками разных цветов. Он решил отрезать первые несколько камней с этой нитки, чтобы сделать из них бусы и подарить своей подруге, Ам Нелли.
Ам Ням знает, что его подруга любит красивые узоры. Поэтому он хочет, чтобы камешки на бусах образовывали регулярный узор. Последовательность камешков S называется регулярной, если она представима в виде S = A + B + A + B + A + ... + A + B + A, где A и B — некоторые последовательности камешков, " + " обозначает конкатенацию последовательностей, слагаемых в этой сумме ровно 2k + 1, среди которых k + 1 слагаемое "A" и k слагаемых "B", причём слагаемые "A" и "B" чередуются. Ам Нелли знает, что её друг — увлекающийся математик, поэтому она с пониманием отнесётся, даже если какая-то из последовательностей A или B окажется пустой.
Помогите Ом Ному определить, какими способами из найденной им нитки можно отрезать первые несколько камешков (не менее одного; возможно, все) таким образом, чтобы они образовывали регулярный узор. Отрезая камешки, Ам Ням не меняет их порядок.
Выходные данные
Выведите строку из n нулей и единиц. Позиция i (1 ≤ i ≤ n) должна либо содержать единицу, если первые i камешков на нитке образуют регулярную последовательность, либо ноль в противном случае.
Примечание
В первом тесте из условия регулярной является как последовательность из первых 6 камешков (если взять A = "", B = "bca"), так и последовательность из первых 7 камешков (если взять A = "b", B = "ca").
Во втором тесте из условия, например, последовательность из первых 13 камешков является регулярной, если взять A = "aba", B = "ba".
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
bcabcab
|
0000011
|
|
2
|
21 2
ababaababaababaababaa
|
000110000111111000011
|