Tutkijat ovat eristäneet Uolevin DNA:n ja pyrkivät ymmärtämään sen rakenteen. Ensimmäisenä toimenaan tutkijat haluavat selvittää, ovatko tietyt DNA:n osat samanlaiset. Voisitko auttaa tutkijoita?

Syöte

Syötteen ensimmäisellä rivillä on merkkijono, jossa on $n$ merkkiä. Tämä merkkijono kuvaa Uolevin DNA:n. Jokainen merkki on A, C, G tai T, ja merkkijono on indeksoitu kokonaisluvuin $1,2,\ldots,n$.

Sitten syötteessä on kokonaisluku $q$ ja sen jälkeen $q$ riviä, joista jokainen on yksi kysely. Kullakin rivillä on kokonaisluvut $a$, $b$ ja $x$. Tällöin kyselynä on selvittää, ovatko kohdista $a$ ja $b$ alkavat $x$ merkin pituiset merkkijonot samat.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: monessako kyselyssä merkkijonot ovat samat.

Rajat

• $1 \le n \le 10^5$
• $1 \le q \le 5 \cdot 10^4$
• $1 \le a, b \le n$
• $1 \le x \le n$

Esimerkki

Syöte:

ACACGTAA
5
1 3 1
1 3 2
1 3 3
3 7 1
3 7 2

Tuloste:

3