Migrated from Lutece 2788 又来攻防啦

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

出于一些不想编的原因， nameless 和 ljj 又来进行攻防演练啦。还是相同的地点，相同的人，相同的规则。两人所使用的系统经过特殊设定，只能接收任何只含有前 $m$ 个小写英文字母的非空字符串作为输入命令。

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

nameless 的任务是在每轮演练中，在 ljj 完成本轮防火墙规则的配置之后，输入一个不被防火墙拦截的命令。由于 nameless 要回去写报告，他想知道每轮演练需要输入的最短字符串的长度是多少。也就是说， nameless 想找到最小的正整数 $k$ ，存在一个长为 $k$ 的字符串 $t=t_1t_2…t_k$ ，使得不存在任意一个长为 $k$ 的序列 $p_1,p_2,…p_k$ 满足 $l≤p_1<p_2<…<p_k≤r$ 且对每个 $i=1,2,…,k$ 均有 $t_i=s_{p_i}$。

Input

第一行包含两个正整数 $m$ $(1≤m≤26)$ 和 $n$ $(1≤n≤200000)$ ，分别表示系统接受的命令的字符集大小和ljj事先准备的字符串的长度。

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

第三行包含一个正整数 $q$ $(1≤q≤200000)$ ，表示攻防演练进行的轮数。

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

Output

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

Samples

2 6
abaabb
3
1 4
2 5
3 6

2
3
2

Resources

2022 UESTC ICPC Training for Dynamic Programming