408958: GYM103389 B 攻防演练

小Q和小C在比特公司的系统中进行攻防演练，这个系统经过特殊设定，只能接收任何只含有前 $$$m$$$ 个小写英文字母的非空字符串作为输入命令。

小Q事先准备了一个长为 $$$n$$$ 的字符串 $$$s = s_1 s_2 \ldots s_n$$$，为了能够在演练时输入到系统中，这个字符串只会包含前 $$$m$$$ 个小写英文字母。攻防演练一共进行 $$$q$$$ 轮，每轮开始时小Q会选择一个 $$$s$$$ 的非空子串 $$$s_{l,r} = s_l s_{l+1} \ldots s_r$$$ 输入到系统中作为本轮演练的防火墙规则。当防火墙规则配置完成之后，对于任何输入到系统中的命令 $$$c$$$，只要 $$$c$$$ 是 $$$s_{l,r}$$$ 的子序列就会被防火墙拦截。

小C的任务是在每轮演练中，在小Q完成本轮防火墙规则的配置之后，输入一个不被防火墙拦截的命令。为了节约时间，小C想知道每轮演练需要输入的最短字符串的长度是多少。也就是说，小C想找到最小的正整数 $$$k$$$，存在一个长为 $$$k$$$ 的字符串 $$$t = t_1 t_2 \ldots t_k$$$，使得不存在任意一个长为 $$$k$$$ 的序列 $$$p_1, p_2, \ldots p_k$$$ 满足 $$$l \le p_1 < p_2 < \ldots < p_k \le r$$$ 且对每个 $$$i=1,2,\ldots,k$$$ 均有 $$$t_i = s_{p_i}$$$。

第一行包含两个正整数 $$$m$$$ ($$$1 \le m \le 26$$$) 和 $$$n$$$ ($$$1 \le n \le 200\,000$$$)，分别表示比特公司系统接受的命令的字符集大小和小Q事先准备的字符串的长度。

第二行包含一个长为 $$$n$$$ 的只包含前 $$$m$$$ 个小写英文字母的字符串，表示小Q事先准备的字符串。

第三行包含一个正整数 $$$q$$$ ($$$1 \le q \le 200\,000$$$)，表示攻防演练进行的轮数。

接下来 $$$q$$$ 行，每行包含两个正整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$)，表示本轮攻防演练中小Q配置字符串 $$$s_{l,r}$$$ 为防火墙规则。

输出 $$$q$$$ 行，每行包含一个正整数，表示本轮攻防演练中小C为了达成目标所需要输入的最短字符串的长度。

2 6
abaabb
3
1 4
2 5
3 6

2
3
2