Codeforces Round 803 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

math

matrices

meet-in-the-middle

number theory

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Long Binary String

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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

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

Output

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

Examples

Input

1

Output

1 2

Input

001

Output

3 4

Input

1111

Output

1 5

Input

00000

Output

-1

Input

00000111110000011111000001111101010

Output

6 37452687

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/12/2024 20:23:55 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|