16. Архивирование

В одном из алгоритмов сжатия используется следующая процедура разбиения данных на блоки:

• Первый символ строки образует первый блок.
• Выбирается наибольший префикс данных $p$, который уже есть среди блоков.
• Если $p$ достиг конца данных, то он является последним блоком.
• Строка $p$+$c$, где $c$ — следующий символ, является следующим блоком.
• Алгоритм переходит ко второму шагу и продолжает обрабатывать данные, начиная с первого символа, который не входит ни в один из блоков.

Например, строка данных 11001110011 будет разбита на блоки 1, 1+0=10, 0, 1+1=11, 10+0=100 и 11. А строка 1111111 будет разбита на блоки 1, 11, 111 и 1.

В единственной строке дана непустая строка $s$, состоящая из $0$ и $1$. Постройте ее разбиение на блоки. Длина строки $s$ не превосходит $1\,000\,000$.

В единственной строке выведите через пробел блоки, на которые разбивается строка $s$.