Podwójne podsłowa

Powiemy, że słowo u jest podsłowem słowa v, jeżeli występuje ono jako spójny (jednokawałkowy) fragment v. Tak więc słowo ababb jest podsłowem słowa abaababbaa, ale nie jest podsłowem słowa abcaab. Powiemy, że słowo u jest podwójnym podsłowem słowa v, jeżeli u jest podsłowem słowa v i u jest postaci ww (w sklejone z w) dla pewnego słowa w. Dla przykładu słowo abab jest podwójnym podsłowem słowa abbaababc.

Dla danego słowa v i danego jego fragmentu należy odpowiedzieć na pytanie, czy jest on podwójnym podsłowem słowa v.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 <= n <= 1.000.000), oznaczająca długość słowa v. W drugim wierszu znajduje się samo słowo v, złożone wyłącznie z małych liter alfabetu angielskiego. Trzeci wiersz wejścia zawiera jedną liczbę całkowitą m (1 <= m <= 500.000), oznaczającą liczbę zapytań. Kolejne m wierszy zawiera po dwie liczby całkowite a oraz b (1 <= a < b <= n; (b-a) jest liczbą nieparzystą), oddzielone pojedynczym odstępem i oznaczające zapytanie o to, czy fragment słowa v zaczynający się na a-tej literce i konczący się na b-tej literce (wraz z tymi literkami) jest podwójnym podsłowem v. Literki słowa v numerujemy przy tym od 1 do n.

Wyjście

Wyjście powinno się składać z m wierszy, zawierających odpowiedzi na zapytania. i-ty wiersz powinien zawierać jedno słowo TAK, jeżeli podany fragment v jest jego podwójnym podsłowem, a NIE w przeciwnym przypadku.

Przykład

Dla danych wejściowych:

10
abbacbacca
5
1 4
3 8
5 8
8 9
1 10

poprawnym wynikiem jest:

NIE
TAK
NIE
TAK
NIE

Słowa występujące w kolejnych zapytaniach to: abba, bacbac, cbac, cc, abbacbacca.