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