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$