Srwudiはトップクラスの生物科学者であり、多くの遺伝子工学プロジェクトに携わっています。そのプロジェクトの一つに、ある種の遺伝子断片の数を研究するものがあります。具体的には、処理されたサンプルDNA文字列 $S$ があり、$S$ のすべての部分文字列が遺伝子である可能性があります。ある部分文字列 $S[l..r]$（$S$ の第 $l$ 文字目から第 $r$ 文字目までで構成される文字列）が回文である場合（文字列 $T$ が回文であるとは、反転させても元の文字列と一致することを指します）、$S[l..r]$ は一つの遺伝子となります。なお、異なる遺伝子が重なり合うこともあります。例えば $aba$ の場合、遺伝子は $S[1..1]=a, S[2..2]=b, S[3..3]=a, S[1..3]=aba$ の4つです。しかし、一つの文字列 $S$ には機能が同じ遺伝子が多数含まれている可能性があります。二つの遺伝子 $T, P$ を二つの文字列とみなしたとき、以下の条件のいずれかを満たす場合にのみ、それらは「機能が異なる」とみなされます。

1. $T$ の長さ $\not= P$ の長さ
2. $T[j] \not= P[j]$ となる位置 $j$ が存在する（$T[j], P[j]$ はそれぞれ位置 $j$ における文字を表す）

例えば $aba$ の場合、機能が異なる遺伝子は $3$ つだけです。Srwudiは、あるDNA文字列の中に機能が異なる遺伝子がいくつ含まれているかを知りたいと考えています。

しかし、研究には困難が伴います。技術的な制限により、Srwudiがサンプル文字列 $S$ を抽出する際、十分な精度を保証できず、文字列 $S$ が多くのDNA断片が絡み合ったものになる可能性があります。そのため、Srwudiはまず抽出したものを長さ $N$ の鎖状の文字列 $A$ に展開します。次に、Srwudiは $Q$ 回の推測を行います。毎回、$A$ の部分文字列 $A[l..r]$ を選択してこれを合法的なDNAとみなし、$A[l..r]$ に含まれる機能が異なる遺伝子の数を算出します。もし $Q$ が十分に大きく、Srwudiの推測が十分に正確であれば、この遺伝子工学プロジェクトは前進します。

しかし、Srwudiが作業を開始しようとしたとき、彼は一つの困難に気づきました。文字列 $S$ に含まれる機能が異なる遺伝子の数を素早く知る方法がわからないのです。そこで彼はあなたに助けを求めました。 Srwudiの推測は盲目的なものではなく、毎回推測した後に得られるデータが次回の推測に影響を与えるため、一部の入力データは暗号化されています。

入力

1行目に整数 $type$ が与えられます。$type=0$ の場合、データは暗号化されていません。$type=1$ の場合、データは暗号化されています。

2行目に2つの整数 $N, Q$ が与えられます。これはサンプル $A$ の長さが $N$ であり、Srwudiの推測回数が $Q$ 回であることを示します。 続く $Q$ 行には、それぞれ2つの整数 $L', R'$ が与えられます。$lastans$ を前回の推測の答えとします（初回の場合は $lastans=0$）。今回の推測における $L, R$ は、$L=L' \oplus (type \times lastans), R=R' \oplus (type \times lastans)$ となります。

出力

$Q$ 行にわたって、各推測に対して $A[L..R]$ に含まれる機能が異なる遺伝子の数を出力してください。

入出力例

入力例 1

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

出力例 1

7
2
5
3

注記

復号後の推測は以下の通りです：

1 7
推測された部分文字列は abbabbb で、機能が異なる遺伝子は a, b, bb, bab, bbb, abba, bbabb の7つです。
4 5
推測された部分文字列は ab で、機能が異なる遺伝子は a, b の2つです。
4 8
推測された部分文字列は abbba で、機能が異なる遺伝子は a, b, bb, bbb, abbba の5つです。
3 5
推測された部分文字列は bab で、機能が異なる遺伝子は a, b, bab の3つです。

制約

すべてのデータにおいて、$Q \leq 2N$ を満たし、復号後の $L, R$ は $1 \leq L \leq R \leq N$ を満たします。