Background

Special for beginners, ^_^

Description

给定一个长度为n的字符串s，有q组询问，每个询问给定L,r，询问s[L..r]中有多少本质不同的回文子串。

Format

Input

第一行一个整数type，若type=0，表示这个数据没有进行加密，若

type=1，表示这个数据进行了加密。

第二行两个整数n,q。

第三行一个字符串s。

接下来q行，每行两个整数L′,r′。记Lastans为上一次询问的答案，

若这是第一次询问，Lastans=0，则这次猜测的L,r为，L=L′⊕(type×

Lastans),r=r′⊕(type×Lastans)。

N<=100000

q ≤ 2n, 且解密后的 L, r 满足 1 ≤ L ≤ r ≤ n。字符串的字符集为小写字母

Output

输出共q行，代表每个询问的答案。

Samples

1
8 4
abbabbba
1 7
3 2
6 10
1 0

7
2
5
2