It is another day of loving binary strings, and Little F has started playing a game with them.

Little F is given a binary string $s$ of length $n$, with indices from $1$ to $n$, where $\forall i\in[1,n], s_i\in \{0,1\}$. He wants to delete several binary substrings.

Specifically, Little F makes $n$ attempts.

In the $i$-th attempt ($i\in[1,n]$), he first writes down the binary representation $t$ of the positive integer $i$ (without leading zeros, with the most significant bit on the left; for example, $10$ can be written as $1010$).

Then, he finds the first occurrence of this binary representation $t$ in $s$ from left to right and deletes this substring.

Note that after deletion, the left and right parts of the string are concatenated to form a new string. Please be aware of the change in indices of the new string.

If the current $t$ does not exist in $s$, Little F makes no changes to the string $s$.

You need to answer, for each attempt, the starting position (left endpoint) of the first occurrence of $t$ in $s$, and how many times $t$ appears in $s$.

Two occurrences are defined as different if and only if their left endpoints are different.

Please pay attention to input and output efficiency.

Input

The first line contains a positive integer $n$ ($1\leq n\leq 1000000$).

The second line contains a string $s$ of length $n$. It is guaranteed that $\forall i\in[1,n], s_i \in \{0, 1\}$.

Output

Output $n$ lines, each containing two integers. The $i$-th line represents the starting position of the first occurrence of $t$ and the number of times it appears in $s$ during the $i$-th attempt.

If the attempt fails, output $-1\ 0$ for that line.

Examples

Input 1

20
01001101101101110010

Output 1

2 11
5 5
4 5
11 1
4 2
7 1
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0