题目描述

小 T 在玩一款游戏，游戏中有彩票。彩票只有中奖与不中奖两种情况。

小 T 玩了一段时间后发现，如果将中奖看作 1，不中奖看作 0 的话，那么一直买彩票后生成的无限长的 01 序列 $T$ 有一个长为 $n$ 的循环节 $S$。具体来讲，$T$ 满足 $T_i=S_{((i-1)\bmod n)+1}$。

定义 $f_i$ 为只考虑前 $i$ 次买彩票时的中奖率，更具体地，若前 $i$ 个数中有 $c_i$ 个1，那么 $f_i=\frac{c_i}{i}$。小T想知道中奖率何时比较高，于是他会有 $q$ 次询问，具体形式如下：

1. 给定整数 $k$，设 $f_w$ 为序列 $f$ 中第 $k$ 大的值，求 $w$ 。
2. 给定整数 $k$，求出 $f_k$ 的排名，若排名不存在，输出 inf。

注意：我们称 $f_a$ 比 $f_b$ 大当且仅当 $f_a>f_b$ 或 $f_a=f_b \wedge a<b$ 。可以证明在这样的定义下，序列 $f$ 中第 $k$ 大的值是存在且唯一的。

输入格式

第一行两个整数 $n,q$，表示循环节长度与询问次数。

第二行一个 01 序列 $S$，表示循环节。

接下来 $q$ 行，每行两个整数 $op,k$，分别表示询问类型和询问参数。$op=1$ 表示第一种询问，即查询第 $k$ 大所在位置，$op=2$ 表示第二种询问，即查询排名。

输出格式

共 $q$ 行，每行一个整数表示答案。

3 6
100
1 1
2 3
1 2
1 3
2 7
2 8

1
inf
2
4
4
8

10 7
1011001000
1 41
1 33
1 4348
1 1235467890
2 19260817
2 729384264
2 274892563

12
19
4968
1058972476
11235477
364692134
240530993

数据范围与提示

对于所有测试数据， $1\leq n\leq 2\times 10^5,1 \leq k \leq 10^{10000},1\leq q\leq 20,op\in \{1,2\}$，保证 $S$ 为 01 序列。