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:
- Given an integer $k$, let $f_w$ be the $k$-th largest value in the sequence $f$. Find $w$.
- 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.
| Subtask | $n\le$ | $k\le$ | Special Property | Score |
|---|---|---|---|---|
| $1$ | $10^5$ | $10^{10000}$ | $S_1=S_2=\dots=S_{n-1}=0,S_n=1$ | $1$ |
| $2$ | $10$ | $1000$ | - | $9$ |
| $3$ | $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$ |