Rezolvare PBinfo #4712

Se consideră o matrice cu n linii și p coloane. Fiecare linie a matricei este o permutare a mulțimii {1, 2, ..., p}.

Cerința

Să se ordoneze lexicografic liniile matricei.

Date de intrare

Fișierul de intrare aperm.in conține pe prima linie numerele n și p separate prin spațiu. Pe următoarele n linii se găsesc câte p numere naturale separate prin spațiu, fiecare linie fiind o permutare a mulțimii {1, 2, ..., p}.

Date de ieșire

Fișierul de ieșire aperm.out va conține n linii. A i-a linie va conține un singur număr natural reprezentând numărul de ordine al liniei din matrice care se află pe poziția i după ordonarea lexicografică a liniilor.

Restricții și precizări

• 3 ≤ n ≤ 50.000
• 2 ≤ p ≤ 16
• Dacă sunt linii identice în permutare, aceste linii se vor afișa în ordinea crescătoare a indicilor.

Exemplu:

aperm.in

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

aperm.out

3
1
5
2
4

Explicație

Cea mai mică permutare din punct de vedere lexicografic este cea de pe linia a treia. Urmează prima linie, apoi a cincea. A doua linie și a patra linie din matrice sunt cele mai mari lexicografic și identice, deci se afișează mai întâi 2, apoi 4.