题目描述
今天也是喜欢二进制串的一天,小 F 开始玩二进制串的游戏。
小 F 给出了一个这里有一个长为 n 的二进制串 s,下标从 1 到 n,且 ∀i∈[1,n],si∈{0,1},他想要删除若干二进制子串。
具体的,小 F 做出了 n 次尝试。
在第 i∈[1,n] 次尝试中,他会先写出正整数 i 的二进制串表示 t(无前导零,左侧为高位,例如 10 可以写为 1010)。
随后找到这个二进制表示 t 在 s 中从左到右 第一次 出现的位置,并删除这个串。
注意,删除后左右部分的串会拼接在一起 形成一个新的串,请注意新串下标的改变。
若当前 t 不在 s 中存在,则小 F 对串 s 不作出改变。
你需要回答每一次尝试中,t 在 s 中第一次出现的位置的左端点以及 t 在 s 中出现了多少次。
定义两次出现不同当且仅当出现的位置的左端点不同。
请注意输入输出效率。
输入格式
第一行一个正整数 n(1≤n≤1000000)。
第二行一个长度为 n 的字符串 s。保证 ∀i∈[1,n],si∈{0,1}。
输出格式
输出共 n 行,每行两个整数,第 i 行表示小 F 进行第 i 次尝试时开头端点的位置以及相应的字符串出现的次数。
若这次尝试失败,则当前行输出 −1 0。
样例1输入
20
01001101101101110010
样例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