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.
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 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.
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.
[Zgłoś rozwiązanie] [Moje zgłoszenia]