Для произвольной бинарной строки \(t\)\(^{\text{∗}}\), пусть \(f(t)\) — количество непустых подпоследовательностей\(^{\text{†}}\) \(t\), которые содержат только символы \(\mathtt{0}\), и пусть \(g(t)\) — это количество непустых подпоследовательностей \(t\), которые содержат хотя бы одну \(\mathtt{1}\).
Обратите внимание, что для \(f(t)\) и \(g(t)\) каждая подпоследовательность считается столько раз, сколько раз она встречается в \(t\). Например, \(f(\mathtt{000}) = 7, g(\mathtt{100}) = 4\).
Назовём единичностью бинарной строки \(t\) значение \(|f(t)-g(t)|\), где \(|z|\) обозначает абсолютное значение \(z\) для любого числа \(z\).
Вам дано целое положительное число \(n\). Найдите бинарную строку \(s\) длины \(n\), такую, чтобы её единичность была как можно меньше. Если строк несколько, вы можете вывести любую из них.
Выходные данные
Для каждого набора входных данных выведите \(s\) на отдельной строке. Если существует несколько ответов, выведите любой.
Примечание
В первом наборе входных данных \(f(t)=1\), потому что существует одна подпоследовательность, содержащая только \(\mathtt{0}\) (подпоследовательность \(\mathtt{0}\)), и \(g(t)=0\), потому что нет подпоследовательностей, содержащих хотя бы одну \(1\). Единичность равна \(|1-0|=1\). Строка \(\mathtt{1}\) также является корректным ответом, так как её единичность равна \(|0-1|=1\).
Во втором наборе входных данных \(f(t)=1\), потому что существует одна непустая подпоследовательность, содержащая только \(\mathtt{0}\), и \(g(t)=2\), потому что существуют две непустые подпоследовательности, содержащие хотя бы одну \(\mathtt{1}\) (\(\mathtt{01}\) и \(\mathtt{1}\)). Таким образом, единичность равна \(|1-2|=1\). Можно показать, что \(1\) — это минимально возможное значение единичности среди всех бинарных строк длины \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
2
3
|
0
01
010
|