题目描述

小 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$ 行，每行一个整数表示答案。

样例 1

输入

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

输出

1
inf
2
4
4
8

$01$ 序列 $T$ 为 $100100100100100100\dots$

序列 $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} $$

可以发现后面的项不会对这几个询问的答案产生影响。

样例 2

输入

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$ 序列。

子任务编号	$n \leq$	$k \leq$	特殊性质	分值
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$
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