Скажем, что строка $$$s$$$ имеет период $$$k$$$, если $$$s_i = s_{i + k}$$$ для всех $$$i$$$ от $$$1$$$ по $$$|s| - k$$$ ($$$|s|$$$ — это длина строки $$$s$$$), и $$$k$$$ — минимальное положительное целое число с этим свойством.

Несколько примеров вычисления периода: для $$$s$$$=«0101» период равен $$$k=2$$$, для $$$s$$$=«0000» период равен $$$k=1$$$, для $$$s$$$=«010» период равен $$$k=2$$$, для $$$s$$$=«0011» период равен $$$k=4$$$.

Вам задана строка $$$t$$$, состоящая только из 0 и 1, и вам нужно найти такую строку $$$s$$$, что:

1. Строка $$$s$$$ состоит только из 0 и 1;
2. Длина $$$s$$$ не превосходит $$$2 \cdot |t|$$$;
3. Строка $$$t$$$ является подпоследовательностью строки $$$s$$$;
4. Строка $$$s$$$ имеет минимальный возможный период среди всех строк, удовлетворяющих условиям 1—3.

Напомним, что $$$t$$$ является подпоследовательностью $$$s$$$, если $$$t$$$ можно получить из $$$s$$$ путем удаления нуля или более элементов (любых) и не меняя порядок оставшихся элементов. Например, $$$t$$$=«011» — это подпоследовательность строки $$$s$$$=«10101».