小 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$ 次询问，具体形式如下：
- 给定整数 $k$，设 $f_w$ 为序列 $f$ 中第 $k$ 大的值，求 $w$ 。
- 给定整数 $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$ 行，每行一个整数表示答案。
样例一
input
3 6 100 1 1 2 3 1 2 1 3 2 7 2 8
output
1 inf 2 4 4 8
explanation
01序列 $T$ 为 100100100100100100...
序列 $f$ 的前 $13$ 项为 $\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{2},\frac{2}{5},\frac{1}{3},\frac{3}{7},\frac{3}{8},\frac{1}{3},\frac{2}{5},\frac{4}{11},\frac{1}{3},\frac{5}{13}$，可以发现后面的项不会对这几个询问的答案产生影响。
样例二
input
10 7 1011001000 1 41 1 33 1 4348 1 1235467890 2 19260817 2 729384264 2 274892563
output
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 序列。
| 子任务编号 | $n\le$ | $k\le$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| $1$ | $10^5$ | $10^{10000}$ | $S_1=S_2=\dots=S_{n-1}=0,S_n=1$ | $1$ |
| $2$ | $10$ | $1000$ | - | $9$ |
| $3$ | $10^5$ | $10^9$ | $9 $ | |
| $4$ | $10^{10000}$ | $op=2$ | $13$ | |
| $5$ | $S_1=1,S_2=S_3=\dots=S_n=0$ | $20$ | ||
| $6$ | $200$ | - | $18$ | |
| $7$ | $10^5$ | $30$ |