Tehtäväsi on muodostaa n \times n -ruudukko, jonka jokaisessa ruudussa on kokonaisluku väliltä 1 \ldots n. Ruudukon täytyy toteuttaa kaksi vaatimusta:

1. Jokainen luku 1 \ldots n esiintyy ruudukossa tarkalleen n kertaa.
2. Ruudukon pysty- ja vaakariveistä tulee muodostua 2n eri summaa.

Esimerkiksi tapauksessa 5 \times 5 yksi mahdollinen ruudukko on seuraava:

Jokainen luku 1 \ldots 5 esiintyy ruudukossa 5 kertaa, ja rivien summat ovat [8,11,12,14,15,16,17,18,19,20].

Syöte

Syötteen ainoalla rivillä on kokonaisluku n.

Tuloste

Tulosta jokin ehdot täyttävä ruudukko. Jos mitään ruudukkoa ei ole olemassa, tulosta vain merkkijono "QAQ".

Esimerkki 1

Syöte:

5

Tuloste:

2 3 1 1 1 
1 5 5 3 3 
2 3 5 2 4 
5 4 5 4 1 
2 3 4 4 2

Esimerkki 2

Syöte:

2

Tuloste:

QAQ

Osatehtävä 1 (35 pistettä)

• 2 \le n \le 10

Osatehtävä 2 (21 pistettä)

• 2 \le n \le 100

Osatehtävä 3 (44 pistettä)

• 2 \le n \le 1000