Задача M. (20081226) Следующая строка

Автор:Жюри зимних сборов 2009   Ограничение времени:2 сек
Входной файл:next.in   Ограничение памяти:64 Мб
Выходной файл:next.out  
Максимальный балл:100  

Условие

Назовём строку из нулей и единиц простой, если она лексикографически меньше любого своего собственного суффикса. Например, строка "00101" простая, а "00000" — нет (любой её собственный суффикс меньше всей строки).

Необходимо по простой строке найти следующую в лексикографическом порядке простую строку такой же длины.

Формат входного файла

Входной файл содержит простую строку длины n (2 ≤ n ≤ 104).

Формат выходного файла

В выходном файле должна находиться следующая в лексикографическом порядке простая строка длины n. Гарантируется, что она существует.

Примеры тестов

Входной файл (next.in) Выходной файл (next.out)
1
00111
01011

0.057s 0.019s 13