Long Binary String

现有一个无穷大的 $01$ 序列，初始全为 $0$。给定一个有限的 $01$ 序列 $S$，每次操作可以将原序列一个长为 $|S|$ 的子段异或上 $S$ ，最终需要使得整个序列只有两个 $1$。 问最终字典序最大的序列的两个 $1$ 分别所处的位置。 $|S|$ $\le$ 35。

There is a binary string $ t $ of length $ 10^{100} $ , and initally all of its bits are $ \texttt{0} $ . You are given a binary string $ s $ , and perform the following operation some times: - Select some substring of $ t $ , and replace it with its XOR with $ s $ . $ ^\dagger $ After several operations, the string $ t $ has exactly two bits $ \texttt{1} $ ; that is, there are exactly two distinct indices $ p $ and $ q $ such that the $ p $ -th and $ q $ -th bits of $ t $ are $ \texttt{1} $ , and the rest of the bits are $ \texttt{0} $ . Find the lexicographically largest $ ^\ddagger $ string $ t $ satisfying these constraints, or report that no such string exists. $ ^\dagger $ Formally, choose an index $ i $ such that $ 0 \leq i \leq 10^{100}-|s| $ . For all $ 1 \leq j \leq |s| $ , if $ s_j = \texttt{1} $ , then toggle $ t_{i+j} $ . That is, if $ t_{i+j}=\texttt{0} $ , set $ t_{i+j}=\texttt{1} $ . Otherwise if $ t_{i+j}=\texttt{1} $ , set $ t_{i+j}=\texttt{0} $ . $ ^\ddagger $ A binary string $ a $ is lexicographically larger than a binary string $ b $ of the same length if in the first position where $ a $ and $ b $ differ, the string $ a $ has a bit $ \texttt{1} $ and the corresponding bit in $ b $ is $ \texttt{0} $ .

The only line of each test contains a single binary string $ s $ ( $ 1 \leq |s| \leq 35 $ ).

If no string $ t $ exists as described in the statement, output -1. Otherwise, output the integers $ p $ and $ q $ ( $ 1 \leq p < q \leq 10^{100} $ ) such that the $ p $ -th and $ q $ -th bits of the lexicographically maximal $ t $ are $ \texttt{1} $ .

1

1 2

001

3 4

1111

1 5

00000

-1

00000111110000011111000001111101010

6 37452687

In the first test, you can perform the following operations. $ $$$\texttt{00000}\ldots \to \color{red}{\texttt{1}}\texttt{0000}\ldots \to \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots $ $ </p><p>In the second test, you can perform the following operations. $ $ \texttt{00000}\ldots \to \color{red}{\texttt{001}}\texttt{00}\ldots \to \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots $ $ </p><p>In the third test, you can perform the following operations. $ $ \texttt{00000}\ldots \to \color{red}{\texttt{1111}}\texttt{0}\ldots \to \texttt{1}\color{red}{\texttt{0001}}\ldots $ $ </p><p>It can be proven that these strings $ t $ are the lexicographically largest ones.</p><p>In the fourth test, you can't make a single bit $ \\texttt{1}$$$, so it is impossible.