Srwudi 是一位頂尖的生物科學家，他參與了許多基因工程工作。其中的一個工程需要研究某個物種基因片段的數目，也就是說，會有一串經過處理的樣本 DNA 串 $S$，$S$ 的每一個子串都可能是一個基因。對於某個子串 $S[l..r]$（表示 $S$ 中第 $l$ 個字元到第 $r$ 個字元組成的串），假如 $S[l..r]$ 是一個回文串（一個串 $T$ 為回文串，當且僅當將 $T$ 反轉後，仍與原串相同），那麼 $S[l..r]$ 就是一個基因。注意，不同的基因可能重疊。比如說 $aba$，就有 4 個基因：$S[1..1]=a, S[2..2]=b, S[3..3]=c, S[1..3]=aba$。但一個串 $S$ 中可能含有許多功能相同的基因，對於兩個基因 $T, P$，將它們視為兩個字串，它們只需要滿足以下條件中的一個，那麼就是不同的：

1. $T$ 的長度 $\not= P$ 的長度
2. 存在一個位置 $j$，滿足 $T[j] \not= P[j]$，其中 $T[j], P[j]$ 分別表示在位置 $j$ 上的字元。

比如對於 $aba$，就只有 3 個功能不同的基因了。對於一個 DNA，Srwudi 想知道這個 DNA 串中會含有多少功能不同的基因。

但研究往往是困難重重的，由於技術有限，Srwudi 提取樣本串 $S$ 時不能保證十分精確，甚至有可能這個串 $S$ 會是許多個 DNA 片段纏繞在一起的。因此，Srwudi 首先將提取出來的東西展開成一條長度為 $N$ 的鏈，設為 $A$。注意 $A$ 依然是一個串，Srwudi 接下來會進行 $Q$ 次猜測，每次他會選擇一段 $A$ 中的子串 $A[l..r]$，並認為這就是一段合法的 DNA，然後算出 $A[l..r]$ 中有多少功能不同的基因。假如 $Q$ 足夠大並且 Srwudi 的猜測足夠準確的話，這個基因工程就能繼續推進了。

然而，正當 Srwudi 準備開始工作時，他意識到一個困難，他無法快速地知道一個串 $S$ 中會有多少功能不同的基因，所以他找到了你，希望你能幫助他。 由於 Srwudi 的猜測不是盲目性的，他每次猜測後獲得的數據會影響下一次的猜測，因此部分輸入數據會進行一定的加密。

輸入格式

第一行一個整數 $type$，若 $type=0$，表示這個數據沒有進行加密；若 $type=1$，表示這個數據進行了加密。

第二行兩個整數 $N, Q$，表示樣本 $A$ 的長度為 $N$，以及 Srwudi 進行的猜測次數為 $Q$。 接下來 $Q$ 行，每行兩個整數 $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

解密後的猜測依次為： 1 7：猜測的子串為 abbabbb，不同功能的基因分別是：a, b, bb, bab, bbb, abba, bbabb 4 5：猜測的子串為 ab，不同功能的基因分別是：a, b 4 8：猜測的子串為 abbba，不同功能的基因分別是：a, b, bb, bbb, abbba 3 5：猜測的子串為 bab，不同功能的基因分別是：a, b, bab

資料範圍

對於所有數據，滿足 $Q \leq 2N$，且解密後的 $L, R$ 滿足 $1 \leq L \leq R \leq N$。