CF1698G.Long Binary String

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}$.

存在一个长度为 $10^{100}$ 的二进制字符串 $t$，初始时其所有比特均为 $\texttt{0}$。你被给定一个二进制字符串 $s$，并可执行如下操作若干次：

• 选取 $t$ 的某个子串，并将其与 $s$ 进行按位异或（XOR）运算后替换原位置。$^\dagger$

经过若干次操作后，字符串 $t$ 恰好包含两个比特 $\texttt{1}$；即存在两个互异的下标 $p$ 和 $q$，使得 $t$ 的第 $p$ 位和第 $q$ 位为 $\texttt{1}$，其余所有比特均为 $\texttt{0}$。

在满足上述约束的所有可能字符串 $t$ 中，找出字典序最大者$^\ddagger$；若不存在这样的字符串，则报告无解。

$^\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}$，则设为 $\texttt{1}$；若 $t_{i+j}=\texttt{1}$，则设为 $\texttt{0}$。

$^\ddagger$ 对于两个等长的二进制字符串 $a$ 和 $b$，若在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 的对应比特为 $\texttt{1}$ 而 $b$ 的对应比特为 $\texttt{0}$，则称 $a$ 的字典序大于 $b$。

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

每个测试用例仅包含一行，其中为一个二进制字符串 $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 \lt q \leq 10^{100}$) such that the $p$-th and $q$-th bits of the lexicographically maximal $t$ are $\texttt{1}$.

如果不存在满足题面描述的字符串 $t$，则输出 $-1$。否则，输出整数 $p$ 和 $q$（$1 \leq p \lt q \leq 10^{100}$），使得字典序最大的 $t$ 的第 $p$ 位和第 $q$ 位均为 $\texttt{1}$。

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$$

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$$

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$$

It can be proven that these strings $t$ are the lexicographically largest ones.

In the fourth test, you can't make a single bit $\texttt{1}$, so it is impossible.

在第一个测试用例中，你可以执行以下操作：

$$\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}$，因此不可能实现。