U111350 重演

yy，强迫症患者，专注中考无法自拔（惨啊~）。据说，他的经历可以通过这道题避免重演。 历史的重演分为两类，一类是历史的正序重演，一类是历史的倒序重演。 yy 把历史上的事件简化为一个大写字母，于是历史就成了一个字符串。yy 想知道，在每件事情发生后，最长的历史进程与当时的进程相同以及最长的历史进程的倒序与当时的进程相同。

给定一个长为 $s$ 由**大写字母**组成的字符串 $c$，对于每一个询问给定的类型 $type$ 和位置 $k$： + 若 $type=1$， 输出字符串 $c_1c_2...c_k$ 的最长前缀的长度使得这个前缀也是这个字符串的后缀。 + 若 $type=2$， 输出字符串 $c_1c_2...c_k$ 的最长前缀的长度使得这个前缀也是这个字符串的后缀的倒序。 tips：一个字符串的前缀和后缀均不包含它本身。

第一行输入两个整数 $s$，$q$。分别表示字符串长度和询问个数。 第二行输入一个长为 $s$ 字符串 $c$，表示人类的历史。 接下来 $q$ 行，每行两个整数，表示每一个询问的 $type$ 和 $k$。

对于每一个询问输出一行，表示答案。

#### 样例1说明： 询问 1：询问字符串为 `A`，没有前后缀，答案为 0。 询问 2：只有 `A` 为公共的前后缀。 询问 3： `AB` 为前缀的且为后缀倒序。 --- #### 数据范围： 对于 $15\%$ 的数据，$s,q \le 20$ 。 对于 $30\%$ 的数据，$s,q \le 100$。 对于 $40\%$ 的数据，$s,q \le 10^3$ 。 另有 $20\%$ 的数据，$type=1$。 另有 $20\%$ 的数据，$type=2$。 对于 $100\%$ 的数据，$1\le s,q \le 10^6$，$type\in \left\{ 1, 2 \right\}$。