Annettuna on kaksi n \times n -ruudukkoa, joista molemmat sisältävät kokonaisluvut 1,2,\ldots,n^2 jossain järjestyksessä. Ruudukon rivit ja sarakkeet on numeroitu kokonaisluvuin 1,2,\ldots,n.

Käytössäsi on seuraavat operaatiot:

1. vaihda keskenään kaksi riviä
2. vaihda keskenään kaksi saraketta

Tehtäväsi on muuttaa ensimmäinen ruudukko toiseksi operaatioiden avulla niin, että operaatioiden määrä on mahdollisimman pieni.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: ruudukoiden koko.

Sitten syötteessä on n riviä, jotka kuvaavat ensimmäisen ruudukon, ja lopuksi n riviä, jotka kuvaavat toisen ruudukon.

Tuloste

Tulosta ensin kokonaisluku k: pienin operaatioiden määrä. Tulosta sitten k riviä, jotka sisältävät operaatiot järjestyksessä.

Jokaisen operaation tulee olla muotoa "1 a b" (vaihda rivit a ja b) tai "2 a b" (vaihda sarakkeet a ja b).

Jos mitään ratkaisua ei ole olemassa, tulosta vain luku -1.

Esimerkki 1

Syöte:

3
1 2 3
4 5 6
7 8 9
2 1 3
8 7 9
5 4 6

Tuloste:

2
2 1 2
1 2 3

Esimerkki 2

Syöte:

3
6 3 7
8 1 4
9 2 5
8 5 2
7 3 1
9 4 6

Tuloste:

-1

Osatehtävä 1 (12 pistettä)

• 1 \le n \le 3

Osatehtävä 2 (55 pistettä)

• 1 \le n \le 50

Osatehtävä 3 (33 pistettä)

• 1 \le n \le 500