题目描述

为了欢迎加入短笛声部的新成员小雅，副首席小铃决定创作一首乐曲。

乐谱可以看作一个长度为 $n$ 的字符串 $S$（只由 a、b 组成）。随后她们制定了一份 $q$ 天的训练计划。
每天给定参数 $l,r$，她们将针对乐曲的一段 $[l,r]$ 进行练习，这次练习分为 $r-l+1$ 轮。

第 $i$ 轮（$1\le i\le r-l+1$）：

• 小铃吹奏区间 $[l,\ l+i-1]$；
• 小雅吹奏区间 $[l+i-1,\ r]$。

定义这一轮的和谐度为：两段吹奏内容的最长公共子串（连续公共部分）的长度。
也就是 $S[l,l+i-1]$ 与 $S[l+i-1,r]$ 的最长公共子串长度，记为 $f_i$。

为了减少输出量，你只需要输出：

其中 $\oplus$ 表示按位异或。

输入格式

第一行三个整数 id, n, q：测试点编号（样例为 0）、乐谱长度与计划天数。
第二行一个长度为 $n$ 的字符串 $S$。
之后 $q$ 行，每行输入两个整数 $l,r$，表示当天的练习参数。

输出格式

共输出 $q$ 行，按顺序对每一天输出一个整数表示答案。

0 8 2
ababbaba
2 4
1 8

5
6

样例解释

第一次练习：$[l,r]=[2,4]$，乐段为 bab。
每一轮演奏区间依次为：

• $\{[2,2],[2,4]\}$，
• $\{[2,3],[3,4]\}$，
• $\{[2,4],[4,4]\}$，

和谐度依次为 $1,1,1$。

第二次练习：$[1,8]$，乐段为 ababbaba。
每一轮的和谐度依次为 $1,2,3,3,3,3,2,1$。

数据范围与提示

• 特殊性质 A：字符串 $S$ 只由字符 a 组成。
• 特殊性质 B：字符串 $S$ 随机生成。
• 特殊性质 C：$l=1$。

对于 100% 的数据：
$1\le n\le 10^5,\ 1\le q\le 30,\ 1\le l\le r\le n$，字符串 $S$ 只由 a、b 两种字符组成。