Srwudi jest wybitnym biologiem molekularnym, który zajmuje się inżynierią genetyczną. Jeden z jego projektów wymaga zbadania liczby fragmentów genów w pewnym gatunku. Mamy do czynienia z przetworzonym łańcuchem DNA $S$, w którym każdy podciąg może być genem. Dla danego podciągu $S[l..r]$, oznaczającego fragment $S$ od znaku na pozycji $l$ do znaku na pozycji $r$, jeśli $S[l..r]$ jest palindromem (ciąg $T$ jest palindromem wtedy i tylko wtedy, gdy po odwróceniu jest identyczny z oryginałem), to $S[l..r]$ jest genem. Zauważ, że różne geny mogą się nakładać. Na przykład w $aba$ mamy 4 geny: $S[1..1]=a, S[2..2]=b, S[3..3]=c, S[1..3]=aba$. Jednak łańcuch $S$ może zawierać wiele genów o tej samej funkcji. Dwa geny $T$ i $P$ traktujemy jako różne, jeśli spełniony jest którykolwiek z poniższych warunków:

1. Długość $T$ jest różna od długości $P$.
2. Istnieje pozycja $j$, taka że $T[j] \neq P[j]$, gdzie $T[j]$ i $P[j]$ oznaczają znaki na pozycji $j$.

Na przykład dla $aba$ istnieją tylko 3 funkcjonalnie różne geny. Srwudi chce wiedzieć, ile funkcjonalnie różnych genów zawiera dany łańcuch DNA.

Badania są jednak trudne. Ze względu na ograniczenia techniczne, Srwudi nie może zagwarantować precyzji przy ekstrakcji próbki $S$, a łańcuch ten może być splotem wielu fragmentów DNA. Dlatego Srwudi najpierw rozwija próbkę w łańcuch o długości $N$, oznaczony jako $A$. $A$ jest również łańcuchem znaków. Następnie Srwudi wykonuje $Q$ zgadnięć. W każdym z nich wybiera podciąg $A[l..r]$, uznaje go za legalny fragment DNA i oblicza, ile funkcjonalnie różnych genów zawiera $A[l..r]$. Jeśli $Q$ jest wystarczająco duże, a zgadnięcia Srwudiego wystarczająco dokładne, inżynieria genetyczna będzie mogła postępować dalej.

Jednak gdy Srwudi przygotowywał się do pracy, zdał sobie sprawę z trudności: nie potrafi szybko określić, ile funkcjonalnie różnych genów znajduje się w łańcuchu $S$. Zwrócił się więc do Ciebie z prośbą o pomoc. Ponieważ zgadnięcia Srwudiego nie są przypadkowe, dane uzyskane po każdym zgadnięciu wpływają na kolejne, dlatego część danych wejściowych jest zaszyfrowana.

Format wejścia

Pierwsza linia zawiera liczbę całkowitą $type$. Jeśli $type=0$, dane nie są zaszyfrowane. Jeśli $type=1$, dane są zaszyfrowane.

Druga linia zawiera dwie liczby całkowite $N$ i $Q$, oznaczające długość próbki $A$ oraz liczbę zgadnięć Srwudiego. Następnie $Q$ linii, każda zawiera dwie liczby całkowite $L', R'$. Niech $lastans$ będzie odpowiedzią na poprzednie zgadnięcie (jeśli jest to pierwsze zgadnięcie, $lastans=0$). Wtedy bieżące $L$ i $R$ wynoszą: $L=L' \oplus (type \times lastans)$, $R=R' \oplus (type \times lastans)$.

Format wyjścia

Wypisz $Q$ linii, każda zawierająca jedną liczbę całkowitą, oznaczającą liczbę funkcjonalnie różnych genów w podciągu $A[L..R]$ dla danego zgadnięcia.

Przykład

Wejście 1

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

Wyjście 1

7
2
5
3

Uwagi

Zdeszyfrowane zgadnięcia to kolejno:

• 1 7: Podciąg: abbabbb, różne funkcjonalnie geny: a, b, bb, bab, bbb, abba, bbabb
• 4 5: Podciąg: ab, różne funkcjonalnie geny: a, b
• 4 8: Podciąg: abbba, różne funkcjonalnie geny: a, b, bb, bbb, abbba
• 3 5: Podciąg: bab, różne funkcjonalnie geny: a, b, bab

Ograniczenia

Dla wszystkich danych wejściowych $Q \leq 2N$, a po zdeszyfrowaniu $1 \leq L \leq R \leq N$.