CSES - Tutkimus
  • Time limit: 4.00 s
  • Memory limit: 128 MB
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