G. Длинная бинарная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть бинарная строка $$$t$$$ длины $$$10^{100}$$$, и изначально все биты в строке равны $$$\texttt{0}$$$. Вам также дана бинарная строка $$$s$$$, и вы можете выполнять следующую операцию:

  • Выберите некоторую подстроку $$$t$$$ и замените ее на побитовое исключающее ИЛИ этой подстроки со строкой $$$s$$$.$$$^\dagger$$$
После некоторого количества операций в строке $$$t$$$ ровно два бита должны быть равны $$$\texttt{1}$$$; иными словами, должны существовать ровно два различных индекса $$$p$$$ и $$$q$$$ такие, что $$$p$$$-й и $$$q$$$-й биты строки $$$t$$$ равны $$$\texttt{1}$$$, а остальные биты равны $$$\texttt{0}$$$.

Найдите лексикографически максимальную $$$^\ddagger$$$ строку $$$t$$$, которая может получиться при выполнении этого условия, или определите, что таких строк получиться не может.

$$$^\dagger$$$ Формально, выберите индекс $$$i$$$ такой, что $$$0 \leq i \leq 10^{100}-|s|$$$. Для всех $$$1 \leq j \leq |s|$$$, если $$$s_j = \texttt{1}$$$, измените значение $$$t_{i+j}$$$. То есть если $$$t_{i+j}=\texttt{0}$$$, положите $$$t_{i+j}=\texttt{1}$$$. Иначе, если $$$t_{i+j}=\texttt{1}$$$, положите $$$t_{i+j}=\texttt{0}$$$.

$$$^\ddagger$$$ Бинарная строка $$$a$$$ лексикографически больше бинарной строки $$$b$$$ такой же длины, если в первой позиции, где $$$a$$$ и $$$b$$$ различаются, строка $$$a$$$ содержит $$$\texttt{1}$$$, а строка $$$b$$$ — $$$\texttt{0}$$$.

Входные данные

Единственная строка содержит бинарную строку $$$s$$$ ($$$1 \leq |s| \leq 35$$$).

Выходные данные

Если нельзя получить подходящую под условие строку $$$t$$$, выведите -1. Иначе выведите два целых числа $$$p$$$ и $$$q$$$ ($$$1 \leq p < q \leq 10^{100}$$$) такие, что в лексикографически максимальной $$$t$$$ $$$p$$$-й и $$$q$$$-й биты равны $$$\texttt{1}$$$.

Примеры
Входные данные
1
Выходные данные
1 2
Входные данные
001
Выходные данные
3 4
Входные данные
1111
Выходные данные
1 5
Входные данные
00000
Выходные данные
-1
Входные данные
00000111110000011111000001111101010
Выходные данные
6 37452687
Примечание

В первом примере можно выполнить следующие операции. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{1}}\texttt{0000}\ldots \to \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots$$$$$$

Во втором примере можно выполнить следующие операции. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{001}}\texttt{00}\ldots \to \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots$$$$$$

В третьем примере можно выполнить следующие операции. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{1111}}\texttt{0}\ldots \to \texttt{1}\color{red}{\texttt{0001}}\ldots$$$$$$

Можно показать, что показанные выше строки $$$t$$$ лексикографически максимальны.

В четвертом примере нельзя сделать ни один бит равным $$$\texttt{1}$$$, поэтому задача невыполнима.