## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Long Binary String Codeforces Solution | Codeforces Problem Solution 2022

G. Long Binary String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a binary string $t$ of length ${10}^{100}$, and initally all of its bits are $\mathtt{\text{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$.${}^{†}$
After several operations, the string $t$ has exactly two bits $\mathtt{\text{1}}$; that is, there are exactly two distinct indices $p$ and $q$ such that the $p$-th and $q$-th bits of $t$ are $\mathtt{\text{1}}$, and the rest of the bits are $\mathtt{\text{0}}$.

Find the lexicographically largest${}^{‡}$ string $t$ satisfying these constraints, or report that no such string exists.

${}^{†}$ Formally, choose an index $i$ such that $0\le i\le {10}^{100}-|s|$. For all $1\le j\le |s|$, if ${s}_{j}=\mathtt{\text{1}}$, then toggle ${t}_{i+j}$. That is, if ${t}_{i+j}=\mathtt{\text{0}}$, set ${t}_{i+j}=\mathtt{\text{1}}$. Otherwise if ${t}_{i+j}=\mathtt{\text{1}}$, set ${t}_{i+j}=\mathtt{\text{0}}$.

Solution Click Below:-  👉
👇👇👇👇👇

${}^{‡}$ 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 $\mathtt{\text{1}}$ and the corresponding bit in $b$ is $\mathtt{\text{0}}$.

Input

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

Output

If no string $t$ exists as described in the statement, output -1. Otherwise, output the integers $p$ and $q$ ($1\le p) such that the $p$-th and $q$-th bits of the lexicographically maximal $t$ are $\mathtt{\text{1}}$.