Problem Description

Today is another day of loving binary strings, and Little F starts playing a game with binary strings.

Little F gives a binary string $s$ of length $n$, indexed from $1$ to $n$, and $\forall i\in[1,n], s_i\in\{0,1\}$. He wants to delete some binary substrings.

Specifically, Little F makes $n$ attempts.

In the $i\in[1,n]$-th attempt, he first writes down the binary string representation $t$ of the positive integer $i$ (without leading zeros, with the left side being the higher bits; 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 will be concatenated to form a new string. Please pay attention to the changes of indices in the new string.

If the current $t$ does not exist in $s$, then Little F does not change the string $s$.

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

Two occurrences are defined to be different if and only if their left endpoint positions are different.

Please pay attention to input and output efficiency.

Input Format

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 Format

Output a total of $n$ lines. Each line contains two integers. The $i$-th line represents, when Little F performs the $i$-th attempt, the starting position of the first occurrence and the number of occurrences of the corresponding string.

If this attempt fails, output $-1\ 0$ on the current line.

20
01001101101101110010

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

Hint

Problem Usage Agreement

From the THUPC2024 (Tsinghua University Student Programming Contest and Intercollegiate Invitational Contest 2024) preliminary round.

The following “this repository” all refer to the official THUPC2024 preliminary round repository (https://github.com/ckw20/thupc2024_pre_public).

1. Any organization or individual may use or reprint the problems in this repository for free.

2. When using the problems in this repository, any organization or individual should do so free of charge and publicly. It is strictly forbidden to profit from these problems or add special access permissions to them.

3. If possible, when using the problems in this repository, please also provide ways to obtain resources such as testdata, reference solutions, and editorials. Otherwise, please attach the GitHub link of this repository.

Translated by ChatGPT 5