Байтазар, король Байтотии организовал масштабную реформу имён своих подданных. Имена жителей Байтотии исторически часто содержат повторяющиеся фразы и Байтазар хочет с одной стороны упростить имена, а с другой, сохранить традиции повторения, а именно Байтазар хочет заменить каждое из имён в Байтотии на имя такой же длины, чтобы при этом множества периодов для старого и нового имён совпали, но имя при этом состояло только из символов «0» и «1». Из всех кандидатов в новое имя Байтазар хочет выбрать лексикографически минимальное.

Натуральное число \(k\) (\(1 \le k \lt n\)) называется периодом строки \(s\) длины \(n\) тогда и только тогда, когда для любого натурального \(i\), такого что \(1 \le i \le n - k\), верно что \(s_i = s_{i + k}\).

Множество периодов для данной строки \(s\) – множество таких чисел \(i\), что \(i\) является периодом \(s\). Обозначим его за Per(\(s\)). К примеру, Per(«ABIABUABIAB») = {6, 9}, Per(«0000») = {1, 2, 3}.

Помогите Байтазару перевести имена его подданных, и, возможно, он разрешит вам сохранить ваше собственное имя!