Uolevi ja Maija ovat löytäneet n omenaa. Yllättävää kyllä, omenoiden painot ovat 1,2,\ldots,n. He haluaisivat jakaa omenat kahteen ryhmään niin, että molemmissa ryhmissä omenoiden yhteispaino on sama.

Tehtäväsi on selvittää, onko tämä mahdollista, ja jos on, näyttää yksi mahdollinen tapa jakaa omenat.

Syöte

Syötteenä on yksi kokonaisluku n: omenoiden määrä.

Tuloste

Jos omenoiden jakaminen on mahdollista, ohjelmasi tulee tulostaa OK, ja muuten QAQ. Jos vastaus on OK, tulosta vielä kaksi riviä, joista ensimmäinen sisältää Uolevin omenat ja toinen sisältää Maijan omenat.

Esimerkki 1

Syöte:

7

Tuloste:

OK
3 4 7
1 2 5 6

Selitys: Molemmissa ryhmissä yhteispaino on 14.

Esimerkki 2

Syöte:

9

Tuloste:

QAQ

Osatehtävä 1 (25 pistettä)

• 1 \le n \le 20

Osatehtävä 2 (25 pistettä)

• 1 \le n \le 1000

Osatehtävä 3 (50 pistettä)

• 1 \le n \le 10^5