有一个长度为$$$10^{100}$$$的二进制字符串$$$t$$$,最初它的所有位都是$$$\texttt{0}$$$。给定一个二进制字符串 $$$s$$$,并执行以下操作几次:
- 选择$$$t$$$的某些子字符串,并将其替换为与$$$s$$$的异或。$$$^\dagger$$$
找到满足这些约束的按字典顺序最大的$$$^\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$$$ 有一个位 $$$\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
输出 #1
1 2
输入 #2
001
输出 #2
3 4
输入 #3
1111
输出 #3
1 5
输入#4
00000
输出#4
-1
输入 #5
00000111110000011111000001111101010
输出 #5
6 37452687
注意
在第一次测试中,您可以执行以下操作。 $$$$$$\texttt{00000}\ldots \至 \color{red}{\texttt{1}}\texttt{0000}\ldots \至 \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots$$$$$$
在第二次测试中,您可以执行以下操作。 $$$$$$\texttt{00000}\ldots \至 \color{red}{\texttt{001}}\texttt{00}\ldots \至 \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots$$$$$$
在第三次测试中,您可以执行以下操作。 $$$$$$\texttt{00000}\ldots \至 \color{red}{\texttt{1111}}\texttt{0}\ldots \至 \texttt{1}\color{red}{\texttt{0001}}\ldots$$$$$$
可以证明这些字符串$$$t$$$是字典序上最大的字符串。
在第四个测试中,你无法做出任何一个位$$$\texttt{1}$$$,所以这是不可能的。