题目描述

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}$。

0 1
9 3
hihehishe
1 7
1 12
2 10

e
0
r

提示

样例 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$。

• 特殊性质 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$ 都相同。