Binary String Deletion Game

Little F loves binary strings, and today he is playing a game with them. He is given a binary string s of length n (indexed from 1 to n) where each character is either 0 or 1. Little F will make n attempts to delete a binary substring from s.

Specifically, on the i-th attempt (1 ≤ i ≤ n):

1. Let t be the binary representation of i without leading zeros (e.g. 10 is represented as 1010). Formally, t is given in latex format as: \(t = \text{bin}(i)\).
2. Find the first occurrence of t in the current string s. If found at position p (1-indexed), count how many occurrences of t appear in s. Note that two occurrences are considered different if and only if their starting positions are different.
3. If t is found, delete the first occurrence of t from s (i.e. remove the substring starting at position p with length |t|); the remaining parts are concatenated to form a new string, and the indices are updated accordingly. If t is not found, s remains unchanged.

For each attempt, output two numbers: the left endpoint of the first occurrence of t in s (output -1 if not found) and the number of occurrences of t in s before deletion. Please pay attention to input/output efficiency.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵ or as constraints specify), which is the length of the binary string s.

The second line contains the binary string s of length n, consisting of characters '0' and '1'.

outputFormat

For each of the n attempts, output a line with two space-separated integers:

• The 1-indexed starting position of the first occurrence of t in the current s (or -1 if t is not found).
• The total number of occurrences of t in s (occurrences are counted by distinct starting positions, and they may overlap).

sample

3
101

1 2
-1 0
-1 0