Srwudi — выдающийся биолог, занимающийся генной инженерией. Один из его проектов требует исследования количества фрагментов генов в образце ДНК. Обработанная цепочка ДНК представляет собой строку $S$, и любая подстрока $S$ может быть геном. Для подстроки $S[l..r]$, состоящей из символов с $l$-го по $r$-й, если $S[l..r]$ является палиндромом (строка $T$ называется палиндромом, если она читается одинаково в обоих направлениях), то $S[l..r]$ считается геном. Заметьте, что разные гены могут перекрываться. Например, в строке $aba$ содержится 4 гена: $S[1..1]=a, S[2..2]=b, S[3..3]=a, S[1..3]=aba$. Однако строка $S$ может содержать много функционально идентичных генов. Два гена $T$ и $P$ считаются различными, если выполняется хотя бы одно из следующих условий:

1. Длина $T$ не равна длине $P$.
2. Существует такая позиция $j$, что $T[j] \not= P[j]$, где $T[j]$ и $P[j]$ — символы на позиции $j$ в соответствующих строках.

Например, в строке $aba$ содержится только 3 функционально различных гена. Srwudi хочет знать, сколько функционально различных генов содержится в данной строке ДНК.

Исследования часто сопряжены с трудностями. Из-за технических ограничений Srwudi не может гарантировать точность при извлечении образца $S$, и строка $S$ может представлять собой множество переплетенных фрагментов ДНК. Поэтому Srwudi сначала разворачивает извлеченный материал в цепочку длины $N$, обозначим её $A$. $A$ также является строкой. Далее Srwudi делает $Q$ предположений: каждый раз он выбирает подстроку $A[l..r]$, считает её допустимым фрагментом ДНК и вычисляет количество функционально различных генов в $A[l..r]$. Если $Q$ достаточно велико, а предположения Srwudi точны, генная инженерия сможет продвинуться вперед.

Однако, готовясь к работе, Srwudi осознал сложность задачи: он не может быстро определить количество функционально различных генов в строке $S$. Поэтому он обратился к вам за помощью. Поскольку предположения Srwudi не случайны, данные, полученные после каждого предположения, влияют на следующее, поэтому часть входных данных зашифрована.

Входные данные

Первая строка содержит целое число $type$. Если $type=0$, данные не зашифрованы. Если $type=1$, данные зашифрованы.

Вторая строка содержит два целых числа $N$ и $Q$, где $N$ — длина образца $A$, а $Q$ — количество предположений Srwudi. Далее следуют $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 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$.