h2. Date de iesire

Pe prima linie a fisierului de iesire $papuci.out$ se va scrie timpul maxim obtinut de Ionel doar din descaltarea si incaltarea perechilor de papuci la trecerea dintr-o camera intr-alta pe parcursul intregii vizite. Pe a doua linie se va scrie un numar $T$ reprezentand numarul de inversari din cele $K$ pe care le-a utilizat pentru a obtine acest timp maxim. Pe linia a 3-a se vor scrie numerele de ordine ale celor $T$ inversari folosite (inversarile sunt numerotate de la $1$ la $K$ in ordinea in care apar in fisierul de intrare).

Pe prima linie a fisierului de iesire $papuci.out$ se va scrie timpul maxim obtinut de Ionel doar din descaltarea si incaltarea perechilor de papuci la trecerea dintr-o camera intr-alta pe parcursul intregii vizite.

h2. Restrictii
* $1 ≤ N, K ≤ 100.000$
* Elementele matricii $A$ sunt numere naturale mai mici sau egale cu $1000$.
* Matricea $A$ nu va fi neaparat simetrica fata de diagonala principala.

* Orice camera $i$ apare cel mult o data in cele $K$ inversari.
* Nu exista doua inversari $(a,b)$ si $(c,d)$ cu $c > a$, $c < b$ si $b < d$.
* Cele $T$ inversari trecute in fisierul de iesire trebuie sa fie distincte.
* In cazul in care exista mai multe solutii care determina timpul maxim corect, oricare din ele este acceptata.

* Orice camera $i$ apare in cel mult una din cele $K$ inversari.
* Nu exista doua inversari $(a,b)$ si $(c,d)$, $a &le; b$, $c &le; d$, astfel incat $c > a$, $c < b$ si $b < d$.

h2. Exemplu
table(example). |_. papuci.in |_. papuci.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 6 3
abccba
1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 5 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 6
4 5
3 3
| 19
|

h3. Explicatie

...

Timpul maxim $19$ se obtine interschimband papucii din camerele $4$ si $5$. Asadar, sirul de papuci inainte de inceperea vizitei in muzeu este $abcbca$.

== include(page="template/taskfooter" task_id="papuci") ==

3569