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