题目描述

今天也是喜欢二进制串的一天，小 F 开始玩二进制串的游戏。

小 F 给出了一个长为 $n$ 的二进制串 $s$，下标从 $1$ 到 $n$，且 $\forall i\in[1,n], s_i\in \{0,1\}$，他想要删除若干二进制子串。

具体的，小 F 做出了 $n$ 次尝试。

在第 $i\in[1,n]$ 次尝试中，他会：

1. 先写出正整数 $i$ 的二进制串表示 $t$（无前导零，左侧为高位，例如 $10$ 可以写为 1010）。
2. 找到这个二进制表示 $t$ 在 $s$ 中从左到右第一次出现的位置，并删除这个子串。
3. 删除后左右部分的串会拼接在一起形成一个新的串，请注意新串下标的改变。

若当前 $t$ 不在 $s$ 中存在，则小 F 对串 $s$ 不作出改变。

你需要回答每一次尝试中：

• $t$ 在 $s$ 中第一次出现的位置的左端点
• $t$ 在 $s$ 中出现了多少次

定义两次出现不同当且仅当出现的位置的左端点不同。

输入格式

第一行一个正整数 $n$（$1\leq n\leq 1000000$）。

第二行一个长度为 $n$ 的字符串 $s$。保证 $\forall i\in[1,n], s_i \in \{0, 1\}$。

输出格式

输出共 $n$ 行，每行两个整数，第 $i$ 行表示小 F 进行第 $i$ 次尝试时：

• 开头端点的位置
• 相应的字符串出现的次数

若这次尝试失败，则当前行输出 -1 0。

样例

输入：

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