#784. 基因

基因

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