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$