小Q有一个字符串s，并且其只由前m个小写字母组成（不一定全部出现），此时他想到了一个难题要考考你。

小Q一共会进行q轮询问，每次他会向你说明两个下标l,r （l <= r）,即将slsl+1....sr构成一个新的的字符串t，现在你的任务是，利用前m个小写字母拼凑出一个最短的字符串（不一定全部使用），使得其不会与t的任意子序列p（t1 < p1 < p2 < p3<.... < pk <= tn）相同。

第一行包括两个整数m(1 <= m <= 26)和n( 1 <= n <= 200000),分别表示约定好的可以使用的小写字母集的大小和字符串s的长度。

第二行包括一个长为n并且只包括前m个小写字母的字符串s。

第三行包括一个整数q，代表要询问的次数。

接下来q行，每行包括两个整数l和r(1 <= l <= r <= n)，即表示选取的字符串的sl-r为字符串t。

输出q行，每行包括一个正整数表示你成功找出的合法字符串的最小长度。

[1,4]即为字串abaa，你可以选取字符串 bb 使得其不会与abaa的任意子序列相同。

[2,5]即为字串baab，你可以选取字符串 aba 使得其不会与baab的任意子序列相同。

[3,6]即为字串aabb，你可以选取字符串 ba 使得其不会与aabb的任意子序列相同。