Sinulle on annettu yksi merkkijono. Tehtäväsi on vastata kyselyihin, ovatko merkkijonon kaksi osajonoa samat.

Syöte

Ensimmäisellä rivillä on merkkijono, jossa on n merkkiä väliltä a–z. Merkit on numeroitu 1, 2, \dots, n.

Toisella rivillä on kokonaisluku q: kyselyiden määrä.

Seuraa q riviä, joista jokaisella on luvut a_1, b_1, a_2 ja b_2: ensimmäisen ja toisen osajonon alku- ja loppukohdat.

Tuloste

Tulosta jokaiselle kyselylle omalle rivilleen joko 10-4, jos osajonot muodostavat saman merkkijonon, tai QAQ, jos eivät.

Esimerkki

Syöte:

aaabaaa
2
1 3 5 7
3 4 4 5

Tuloste:

10-4
QAQ

Rajat

• 1 \le n \le 10^6
• 1 \le q \le 10^5
• 1 \le a_i \le b_i \le n