题目描述

对于给定的由大小写字母混合构成的字符串$s$，下标从$1$开始，我们需要将每一个$k$的倍数位进行大小写转换(即对于第$k,2\times k...$位)，

而对于其他位置，无论大小写，直接使用其$ASCII$码替换其在字符串中的位置(从$1$开始)。

由于这样得到的字符串可能非常长，所以，我们一共会提出$q$次询问，每一次询问给定一个区间$[l,r]$，你只需要输出这 个区间中的全部字符。

输入描述

第一行输入一个正整数$k(1 \le k \le 10^5)$，代表进位倍数。

第二行输入一个长度为$1\le len(s) \le 10^6$，由大小写字母构成的字符串$s$，代表需要进行操作的字符串。

第三行输入一个正整数$q(1 \le q \le 100)$，代表询问次数。

此后$q$行，每行输入两个正整数$l,r(1 \le l \le r \le len(s))$代表询问的区间。

在这里，$len(s)$代表操作全部完成后的字符串长度。除此之外，保证输出的字符数量不超过$2\times 10^5$

输出描述

对于每一次询问，新起一行。输出一个字符串，代表询问的区间中的全部字符。

样例

输入

2
аABbсC
3
1 1
2 4
8 9

输出

9
7a6
9c

样例解释

根据题意，需要对$2,4,6$位进行大小写转换，转换后得到$aaBBcc$。

随后，对于$1,3,5$位，使用其$ASCII$码替换其在字符串中的位置，最终得到字符串$97a66B99c$。