Organizatorzy pewnego konkursu informatycznego zaprosili do udziału uczniów różnych klas. Po kilku dniach konkursu okazało się, że rozwiązania uczniów z tych samych klas są bardzo podobne. Organizatorzy bardzo się ucieszyli i postanowili odtworzyć podział na klasy na podstawie podobnieństw między rozwiązaniami uczestników. Jednak ponieważ rozwiązań jest bardzo, bardzo wiele, proces ten trzeba zautomatyzować. Potrzebny jest zatem program, który mając dane dwa rozwiązania będzie porównywał ich fragmenty, informując organizatorów, czy są one identyczne, czy nie.
W pierwszych dwóch liniach wejścia znajdują się dwa ciągi znakowe,
każdy nie dłuższy niż 200 000 znaków, składające się z małych i
wielkich liter alfabetu angielskiego oraz cyfr - są to dwa porównywane
rozwiązania uczestników. Następnie na wejściu znajduje się conajwyżej
500 000 zapytań. Każde z nich jest opisane trzema liczbami a, b, n,
które oznaczają kolejno: początek fragmentu w rozwiązaniu pierwszym,
początek fragmentu w rozwiązaniu drugim oraz długość obu fragmentów.
Organizatorzy zauważyli, że oba fragmenty muszą mieć taką samą długość
- w przeciwnym wypadku nie mogłyby być identyczne! Wejście kończy się
zapytaniem 0 0 0
Dla każdego zapytania należy wypisać jedno słowo: TAK
jeżeli fragment rozwiązania pierwszego rozpoczynający się na a-tej literze i mający długość n jest identyczny z fragmentem rozwiązania drugiego rozpoczynającego się na b-tej literze i mającego długość n, lub NIE
w przeciwnym wypadku. Pierwsza litera każdego rozwiązania ma numer 1.
Dla danych wejściowych
LoremipsumdolorsitametconsecteturadipiscingelitIntegernonmaurissed
SedmipurusrhoncussedconvalliseuplaceratataugueDuisjustocrasamet
5 4 3
5 4 4
23 21 3
19 60 4
0 0 0
poprawną odpowiedzią jest
TAK
NIE
TAK
TAK