题目描述
给定一个长度为 $n$ 且只包含小写字母的字符串 $s$，其下标从 $1$ 开始。
定义一次修改为对 $s$ 同时进行下面的两种操作：
- 将 $s$ 中所有为 $\texttt{he}$ 的子串替换为 $\texttt{she}$；
- 将 $s$ 中所有为 $\texttt{his}$ 的子串替换为 $\texttt{her}$。
例如，对 $\texttt{hihehishe}$ 进行一次操作后，该字符串会变为 $\texttt{hishehershe}$。
现有 $q$ 次询问，第 $i$ 次询问给出两个参数 $k_i,x_i$，你需要求出对 $s$ 进行 $k_i$ 次修改后 $s$ 的第 $x_i$ 个字符，或报告不存在第 $x_i$ 个字符。询问之间互相独立。
输入格式
本题有多组测试数据。
输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据组数。样例满足 $c=0$。
接下来依次输入每组测试数据。对于每组测试数据：
- 第一行两个正整数 $n,q$。
- 第二行一个长度为 $n$ 的字符串 $s$。
- 接下来 $q$ 行，第 $i$ 行两个正整数 $k_i,x_i$。
输出格式
对于每组测试数据，输出 $q$ 行，第 $i$ 行包含一个字符：
- 若对 $s$ 进行 $k_i$ 次修改后，$s$ 中存在第 $x_i$ 个字符，则输出该字符；
- 若对 $s$ 进行 $k_i$ 次修改后，$s$ 中不存在第 $x_i$ 个字符，则输出 $\texttt{0}$。
样例 1 输入
0 1 9 3 hihehishe 1 7 1 12 2 10
样例 1 输出
e 0 r
样例 1 解释
在该组样例的唯一一组测试数据中，$s=\texttt{hihehishe}$。
对 $s$ 进行一次修改后，$s$ 会变为 $\texttt{hishehershe}$，此时 $s$ 中的第 $7$ 个字符为 $\texttt{e}$ 且不存在第 $12$ 个字符。
对 $s$ 进行两次修改后，$s$ 会变为 $\texttt{hersheshersshe}$，此时 $s$ 中的第 $10$ 个字符为 $\texttt{r}$。
样例 2
见 right/right2.in 与 right/right2.ans。
该组样例满足测试点 $3$ 的限制。
样例 3
见 right/right3.in 与 right/right3.ans。
该组样例满足测试点 $4$ 的限制。
样例 4
见 right/right4.in 与 right/right4.ans。
该组样例满足测试点 $5$ 的限制。
样例 5
见 right/right5.in 与 right/right5.ans。
该组样例满足测试点 $10$ 的限制。
样例 6
见 right/right6.in 与 right/right6.ans。
该组样例满足测试点 $13$ 的限制。
样例 7
见 right/right7.in 与 right/right7.ans。
该组样例满足测试点 $20$ 的限制。
数据范围
对于所有测试数据，保证：
- $1 \le T \le 5$；
- $1 \le n,q \le 2\times10^5$；
- $s$ 中只包含小写字母；
- $1 \le k_i,x_i \le 10^9$。
| 测试点编号 | $n \le$ | $q \le$ | $k_i \le$ | 特殊性质 |
|---|---|---|---|---|
| $1$ | $200$ | $2\times10^5$ | $200$ | AB |
| $2$ | $200$ | $2\times10^5$ | $200$ | A |
| $3$ | $200$ | $2\times10^5$ | $200$ | 无 |
| $4$ | $2000$ | $2\times10^5$ | $10^9$ | AB |
| $5$ | $2000$ | $2\times10^5$ | $10^9$ | A |
| $6,7$ | $2000$ | $2\times10^5$ | $10^9$ | 无 |
| $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$ | 无 |
| $19,20$ | $2\times10^5$ | $2\times10^5$ | $10^9$ | 无 |
- 特殊性质 A：若 $s_i=\texttt{i}$ 且 $i \ne n$，则 $s_{i+1} \ne \texttt{h}$。
- 特殊性质 B：若 $s_i=\texttt{i}$ 且 $i \ne n$，则 $s_{i+1} \ne \texttt{s}$。
- 特殊性质 C：保证任意时刻 $s$ 中 $\texttt{he}$ 子串的数量不大于 $3$。
- 特殊性质 D：保证 $k_i$ 都相同。