Fişierul intrare/ieşire:	colorfulconflict.in, colorfulconflict.out	Sursă	Algoritmiada 2019 Runda PreONI
Autor	Mihai Calancea, Tamio-Vesa Nakajima	Adăugată de	Alexandru Petrescu •alexpetrescu
Timp execuţie pe test	1 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Colorfulconflict

Se da o matrice de N linii si N coloane. Fiecare celula (i, j) contine culoarea A_i,j. Se considera boundingbox-ul unei culori x ca fiind dreptunghiul de arie minima cu laturile paralele cu cele ale matricei care include toate celulele unde se afla culoarea x. Se considera ca doua culori x si y se afla in conflict daca si numai daca boundingbox-urile lor se suprapun (au intersectie de arie nenula). Gasiti 3 culori pentru care, oricum as alege doua, ele sa nu fie in conflict.

Date de intrare

Fişierul de intrare colorfulconflict.in contine numarul N pe prima linie. Pe urmatoarele N linii se afla cate N numere, culorile A_i,j.

Date de ieşire

În fişierul de ieşire colorfulconflict.out se afla, in cazul in care nu exista 3 culori cu proprietatea ceruta, numarul -1. In schimb, daca exista, se vor afisa cele 3 numere care identifica cele 3 culori gasite.

Restricţii

• 1 ≤ N ≤ 1.000
• 1 ≤ A_i,j ≤ 1.000.000
• Pentru 33% din punctaj, A_i,j ≤ 100
• Pentru 7% din punctaj, N ≤ 5
• Pentru 11% din punctaj, N ≤ 10
• Pentru 16% din punctaj, N ≤ 20
• Pentru 24% din punctaj, N ≤ 50
• Pentru 49% din punctaj, N ≤ 200

Exemplu

Explicaţie

In primul exemplu nu exista 3 culori astfel incat orice pereche de culori as alege din cele 3, ele sa nu fie in conflict.

In al doilea exemplu, solutiile posibile sunt:

• 3 6 9
• 4 6 9
• 5 7 9
• 5 6 7
• 5 8 9
• 5 6 8
• 5 6 9
• 3 7 9
• 3 6 7
• 4 7 9
• 4 6 7
• 6 7 9
• 4 8 9
• 4 6 8
• 6 8 9

De asemenea, toate permutarile fiecarei solutii sunt corecte, pentru ca ordinea in care afisam numerele in fisierul de iesire nu este relevanta.

Cum se trimit solutii?