Little T is playing a game that involves a lottery. The lottery has two outcomes: winning and not winning.

After playing for a while, Little T discovers that if winning is represented as 1 and not winning as 0, the infinitely long 01 sequence $T$ generated by continuously buying lottery tickets has a periodic segment $S$ of length $n$. Specifically, $T$ satisfies $T_i=S_{((i-1)\bmod n)+1}$.

Define $f_i$ as the winning rate considering only the first $i$ lottery tickets. More specifically, if there are $c_i$ ones in the first $i$ numbers, then $f_i=\frac{c_i}{i}$. Little T wants to know when the winning rate is relatively high, so he has $q$ queries of the following forms:

1. Given an integer $k$, let $f_w$ be the $k$-th largest value in the sequence $f$. Find $w$.
2. Given an integer $k$, find the rank of $f_k$. If the rank does not exist, output inf.

Note: We say $f_a$ is greater than $f_b$ if and only if $f_a > f_b$ or $f_a = f_b \land a < b$. It can be proven that under this definition, the $k$-th largest value in the sequence $f$ exists and is unique.

Input

The first line contains two integers $n$ and $q$, representing the length of the periodic segment and the number of queries, respectively.

The second line contains a 01 sequence $S$, representing the periodic segment.

The next $q$ lines each contain two integers $op$ and $k$, representing the query type and the query parameter. $op=1$ denotes the first type of query (finding the position of the $k$-th largest value), and $op=2$ denotes the second type of query (finding the rank).

Output

Output $q$ lines, each containing an integer representing the answer.

Examples

Input 1

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

Output 1

1
inf
2
4
4
8

Note 1

The 01 sequence $T$ is 100100100100100100...

The first $13$ terms of the sequence $f$ are $\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}$. It can be observed that subsequent terms do not affect the answers to these queries.

Input 2

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

Output 2

12
19
4968
1058972476
11235477
364692134
240530993

Constraints

For all test data, $1\leq n\leq 2\times 10^5, 1 \leq k \leq 10^{10000}, 1\leq q\leq 20, op\in \{1,2\}$, and $S$ is guaranteed to be a 01 sequence.