Srwudi is a top-tier biological scientist who works on many genetic engineering projects. One of these projects requires studying the number of gene fragments in a certain species. Specifically, there is a processed sample DNA string $S$, where every substring of $S$ could potentially be a gene. For a substring $S[l..r]$, which represents the string formed by the characters from index $l$ to index $r$ of $S$, if $S[l..r]$ is a palindrome (a string $T$ is a palindrome if and only if it remains the same when reversed), then $S[l..r]$ is a gene. Note that different genes may overlap. For example, in $aba$, there are 4 genes: $S[1..1]=a, S[2..2]=b, S[3..3]=c, S[1..3]=aba$. However, a string $S$ may contain many genes with the same function. For two genes $T$ and $P$, treated as two strings, they are considered different if and only if they satisfy one of the following conditions:

1. The length of $T$ is not equal to the length of $P$.
2. There exists a position $j$ such that $T[j] \neq P[j]$, where $T[j]$ and $P[j]$ denote the characters at position $j$ in $T$ and $P$, respectively.

For example, in $aba$, there are only 3 functionally distinct genes. For a given DNA string, Srwudi wants to know how many functionally distinct genes it contains.

Research is often fraught with difficulties. Due to technical limitations, Srwudi cannot guarantee that the extracted sample string $S$ is perfectly precise; it is even possible that $S$ consists of many DNA fragments tangled together. Therefore, Srwudi first unfolds the extracted material into a chain of length $N$, denoted as $A$. Note that $A$ is still a string. Srwudi then makes $Q$ guesses. Each time, he selects a substring $A[l..r]$ and considers it a valid DNA segment, then calculates how many functionally distinct genes are in $A[l..r]$. If $Q$ is large enough and Srwudi's guesses are accurate enough, this genetic engineering project can proceed.

However, just as Srwudi was about to start, he realized a difficulty: he cannot quickly determine how many functionally distinct genes are in a string $S$. Therefore, he has come to you, hoping you can help him. Since Srwudi's guesses are not random, the data obtained after each guess affects the next one; therefore, some input data is encrypted.

Input

The first line contains an integer $type$. If $type=0$, the data is not encrypted. If $type=1$, the data is encrypted.

The second line contains two integers $N$ and $Q$, representing the length of the sample $A$ and the number of guesses Srwudi makes, respectively. The next $Q$ lines each contain two integers $L', R'$. Let $lastans$ be the answer to the previous guess. If this is the first guess, $lastans=0$. The $L$ and $R$ for the current guess are $L=L' \oplus (type \times lastans)$ and $R=R' \oplus (type \times lastans)$.

Output

Output $Q$ lines, each containing an integer representing the number of functionally distinct genes contained in $A[L..R]$ for that guess.

Examples

Input 1

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

Output 1

7
2
5
3

Note 1

The decrypted guesses are as follows:

1 7
The guessed substring is abbabbb, and the functionally distinct genes are: a, b, bb, bab, bbb, abba, bbabb
4 5
The guessed substring is ab, and the functionally distinct genes are: a, b
4 8
The guessed substring is abbba, and the functionally distinct genes are: a, b, bb, bbb, abbba
3 5
The guessed substring is bab, and the functionally distinct genes are: a, b, bab

Constraints

For all data, $Q \leq 2N$, and the decrypted $L, R$ satisfy $1 \leq L \leq R \leq N$.