P13841 芳权多

Yuki 有一个长度为 $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 解释 在该组样例的唯一一组测试数据中，$s=\texttt{hihehishe}$。 对 $s$ 进行一次修改后，$s$ 会变为 $\texttt{hishehershe}$，此时 $s$ 中的第 $7$ 个字符为 $\texttt{e}$ 且不存在第 $12$ 个字符。 对 $s$ 进行两次修改后，$s$ 会变为 $\texttt{hersheshersshe}$，此时 $s$ 中的第 $10$ 个字符为 $\texttt{r}$。 ### 数据范围 对于所有测试数据，保证： - $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$ 都相同。