Given a string $s$ of length $n$ consisting only of lowercase letters, with 1-based indexing.
Define a modification as performing the following two operations on $s$ simultaneously:
- Replace all occurrences of the substring $\texttt{he}$ in $s$ with $\texttt{she}$.
- Replace all occurrences of the substring $\texttt{his}$ in $s$ with $\texttt{her}$.
For example, after one operation on $\texttt{hihehishe}$, the string becomes $\texttt{hishehershe}$.
There are $q$ queries. Each query $i$ provides two parameters $k_i$ and $x_i$. You need to find the $x_i$-th character of $s$ after $k_i$ modifications, or report that the $x_i$-th character does not exist. Queries are independent of each other.
Input
The first line contains two positive integers $c$ and $T$, representing the test case ID and the number of test cases, respectively. The sample satisfies $c=0$.
Each test case is described as follows: - The first line contains two positive integers $n$ and $q$. - The second line contains a string $s$ of length $n$. - The next $q$ lines each contain two positive integers $k_i$ and $x_i$.
Output
For each test case, output $q$ lines. The $i$-th line contains a single character: - If the $x_i$-th character exists in $s$ after $k_i$ modifications, output that character. - If the $x_i$-th character does not exist in $s$ after $k_i$ modifications, output $\texttt{0}$.
Examples
Input 1
0 1 9 3 hihehishe 1 7 1 12 2 10
Output 1
e 0 r
Note 1
In the only test case of this sample, $s=\texttt{hihehishe}$.
After one modification, $s$ becomes $\texttt{hishehershe}$. The 7th character is $\texttt{e}$, and the 12th character does not exist.
After two modifications, $s$ becomes $\texttt{hersheshersshe}$. The 10th character is $\texttt{r}$.
Examples 2-7
See right/right2.in and right/right2.ans through right/right7.in and right/right7.ans. These samples satisfy the constraints of test points 3, 4, 5, 10, 13, and 20, respectively.
Constraints
For all test cases, it is guaranteed that: - $1 \le T \le 5$; - $1 \le n,q \le 2\times10^5$; - $s$ contains only lowercase letters; - $1 \le k_i,x_i \le 10^9$.
| Test Point ID | $n \le$ | $q \le$ | $k_i \le$ | Special Property |
|---|---|---|---|---|
| $1$ | $200$ | $2\times10^5$ | $200$ | AB |
| $2$ | $200$ | $2\times10^5$ | $200$ | A |
| $3$ | $200$ | $2\times10^5$ | $200$ | None |
| $4$ | $2000$ | $2\times10^5$ | $10^9$ | AB |
| $5$ | $2000$ | $2\times10^5$ | $10^9$ | A |
| $6,7$ | $2000$ | $2\times10^5$ | $10^9$ | None |
| $8$ | $2\times10^5$ | $2\times10^5$ | $10^9$ | AB |
| $9$ | $2\times10^5$ | $2\times10^5$ | $10^9$ | A |
| $10,11$ | $2\times10^4$ | $2\times10^4$ | $10^9$ | C |
| $12$ | $2\times10^5$ | $2\times10^5$ | $10^9$ | C |
| $13,14$ | $2\times10^4$ | $2\times10^4$ | $10^9$ | D |
| $15$ | $2\times10^5$ | $2\times10^5$ | $10^9$ | D |
| $16\sim18$ | $2\times10^4$ | $2\times10^4$ | $10^9$ | None |
| $19,20$ | $2\times10^5$ | $2\times10^5$ | $10^9$ | None |
- Special Property A: If $s_i=\texttt{i}$ and $i \ne n$, then $s_{i+1} \ne \texttt{h}$.
- Special Property B: If $s_i=\texttt{i}$ and $i \ne n$, then $s_{i+1} \ne \texttt{s}$.
- Special Property C: The number of $\texttt{he}$ substrings in $s$ is guaranteed to be no more than $3$ at any time.
- Special Property D: All $k_i$ are guaranteed to be the same.