sp

Se dă un șir $S$ format din litere mici ale alfabetului englez. O secvență din şir este palindromică dacă prin parcurgerea sa de la dreapta la stânga se obține același cuvânt precum la parcurgerea de la stânga la dreapta.

Cerință

Se formulează $m$ întrebări de forma $i$, $j$, $k$ cu semnificația: pornind de la secvența formată din caracterele dintre indicii $i$ și $j$ inclusiv și având posibilitatea să o extindem în total cu maximum $k$ caractere în $S$ (imediat în stânga poziției $i$ și/sau imediat în dreapta poziției $j$), putem să obținem o secvență palindromică?

Date de intrare

Fișierul de intrare sp.in conține pe prima linie un șir $S$ format din litere mici ale alfabetului englez, neseparate prin spații. Pe linia a doua se găsește numărul de interogări $m$. Pe fiecare dintre următoarele $m$ linii se găsesc câte trei numere $i$, $j$ și $k$ (separate prin spațiu), reprezentând indicele de început, cel de final pentru câte o secvență și numărul maxim de caractere cu care eventual o putem extinde.

Date de ieșire

Fișierul de ieșire sp.out va conține o singură linie pe care vor fi scrise $m$ valori $0$ sau $1$, neseparate prin spații. Dacă din cea de a $i$-a interogare, dintre cele $m$ din fișierul de intrare, putem forma un palindrom în condițiile din enunț, al $i$-lea număr din fișier va fi $1$, iar în caz contrar va fi $0$.

Restricții și precizări

• Notăm cu $n$ lungimea şirului $S$
• $1 \leq n \leq 200 \ 000$
• $1 \leq m \leq 200 \ 000$
• $0 \leq k \leq 5$
• La fiecare interogare dată sub forma $i \ j \ k$, avem $1 \leq i \leq j \leq n$
• Şirul $S$ este indexat de la $1$.
• Pentru teste în valoare de $23$ de puncte: $1 \leq n \leq 2 \ 000$, $1 \leq m \leq 2 \ 000$, și $k = 0$ pentru toate interogările.
• Pentru alte teste în valoare de $11$ puncte avem $1 \leq n \leq 2 \ 000$, $1 \leq m \leq 2 \ 000$.
• Pentru alte teste în valoare de $45$ de puncte avem $1 \leq n \leq 2 \ 000$, $1 \leq m \leq 200 \ 000$.
• Pentru alte teste în valoare de $21$ de puncte se păstrează restricțiile generale.

Exemplu

sp.in

abaaaac
6
1 2 0
1 2 1
2 4 1
2 4 2
1 2 0
2 2 1

sp.out

010001

Explicație

La prima interogare, $k = 0$ iar secvența dată nu este palindromică, deci se scrie la ieșire $0$.

La a doua interogare este vorba despre aceeași secvență dar acum $k = 1$. Deci putem să o extindem cu un caracter. Se poate cu acela din dreapta și obținem secvența aba care este palindromică.

La a treia interogare, secvența formată baa nu este palindromică iar prin extinderea cu un caracter obținem secvențele abaa (extinzând în stânga) sau baaa (extinzând în dreapta). Niciuna dintre aceste secvențe nu este palindromică.

La a patra interogare avem secvența baa și o putem extinde cu până la două caractere: avem variantele: cu un caracter din stânga și obținem abaa, cu un caracter din dreapta și obținem baaa, cu un caracter din stânga și unul din dreapta și obținem abaaa, cu două caractere din dreapta și obținem baaaa. Nu putem extinde cu două caractere în stânga pentru că nu avem.

A cincea interogare este aceeași cu prima și rezultatul este $0$, iar a șasea interogare conține un interval dintr-un element, iar acesta reprezintă o secvență palindromică.