Sinulle on annettu taulukko, joka sisältää luvut 1,2,\ldots,n jossakin järjestyksessä. Tehtäväsi on toteuttaa seuraavat kyselyt:

• vaihda keskenään kohdissa a ja b olevat luvut
• selvitä, onko väli a \ldots b kaunis

Taulukon väli on kaunis, jos jokainen luku on yhtä suurempi kuin edellinen luku, jos välin luvut järjestetään pienimmästä suurimpaan.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja q: taulukon koko ja kyselyiden määrä. Taulukko on indeksoitu 1,2,\ldots,n.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\ldots,x_n: taulukon sisältö. Taulukko on lukujen 1,2,\ldots,n permutaatio.

Sitten syötteessä on q riviä, jotka kuvaavat kyselyt. Jokainen rivi on toinen seuraavista:

• ! a b: vaihda keskenään indeksien a ja b luvut
• ? a b: selvitä, onko väli a \ldots b kaunis

Tuloste

Ohjelmasi tulee tulostaa jokaisesta ?-kyselystä vastaus "10-4" (väli on kaunis) tai "QAQ" (väli ei ole kaunis).

Esimerkki

Syöte:

8 3
8 5 2 1 4 6 7 3
? 4 7
! 2 4
? 4 7

Tuloste:

QAQ
10-4

Osatehtävä 1 (12 pistettä)

• 1 \le n, q \le 1000
• 1 \le a \le b \le n

Osatehtävä 2 (25 pistettä)

• 1 \le n \le 10^5
• 1 \le q \le 1000
• 1 \le a \le b \le n

Osatehtävä 3 (63 pistettä)

• 1 \le n, q \le 10^5
• 1 \le a \le b \le n