Long Binary String
Contest: Codeforces Round 803 (Div. 2)
Difficulty rating: 2900
Tags: bitmasks, math, matrices, meet-in-the-middle, number theory

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

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

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

Output format:
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}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
1

Example output:
1 2

Example input:
001

Example output:
3 4

Editorial:
Ignore leading zeroes of $$$s$$$. We can add them back at the end.
Let's view the string as a polynomial $$$P(x)$$$ in $$$\mathrm{GF}(2)$$$. Then in an operation we can multiply $$$P(x)$$$ by any monomial $$$x^k$$$ for some $$$k$$$, so after some number of operations we can multiply $$$P(x)$$$ by some other polynomial $$$Q(x)$$$.
At the end, we have a string with two flipped bits. We can in fact make the first character equal to $$$1$$$ by finding the smallest $$$k$$$ such that $$$P(x)Q(x) = x^k + 1$$$. Such a $$$k$$$ exists, because the constant term of $$$P$$$ is $$$1$$$ and $$$Q$$$ is arbitrary. Rewrite this as $$$x^k \equiv 1 \pmod{P(x)}$$$. Now it's clear that the answer is a divisor of the order of $$$x$$$ in $$$P(x)$$$.
We can use polynomial factoring algorithms or baby-step-giant-step and meet in the middle. The time complexity is $$$\mathcal{O}(2^{|s|/2} |s|^2)$$$ or $$$\mathcal{O}(2^{|s|/2} |s|)$$$.