Dupa multi ani de cand isi doreste acest lucru, Ionel are in sfarsit ocazia sa viziteze muzeul X. Ca orice vizitator, Ionel trebuie sa respecte regulamentul muzeului, astfel ca ghidul i-l explica la intrare. Baiatul va vizita cele $N$ camere ale muzeului in ordine, de la camera $1$ la camera $N$. In prima camera, va incalta o pereche de papuci (proprietarii muzeului vor sa protejeze astfel covoarele de o inestimabila valoare), iar in fiecare din camerele urmatoare va da jos perechea de papuci curenta si va lua alta pereche pe care o va purta doar in camera respectiva. Papucii sunt de $26$ de tipuri (etichetate cu literele de la $'a'$ la $'z'$), iar fiecare camera a muzeului dispune de o pereche dintr-unul din aceste tipuri. Timpul in care Ionel da jos papucii de tipul $i$ si incalta papucii de tipul $j$ este dat de elementul $A[i][j]$ al unei matrice $A$ furnizate la intrarea in muzeu.

Baiatul isi doreste o vizita cat mai lunga in muzeu, de aceea ghidul ii prezinta Regula Vizitatorilor Speciali. Ionel primeste o lista de $K$ perechi $(a, b)$ de camere si poate decide pana sa isi inceapa vizita ce perechi sa aleaga dintre acestea si pentru fiecare sa schimbe intre ei papucii din camera $a$ cu papucii din camera $b$. Apoi se va bucura de vizita si va profita de timpul cat schimba papucii punand cat mai multe intrebari ghidului.

Baiatul isi doreste o vizita cat mai lunga in muzeu, de aceea ghidul ii prezinta Regula Vizitatorilor Speciali. El primeste o lista de $K$ perechi de camere $(a, b)$ si poate decide pana sa isi inceapa vizita ce perechi sa aleaga dintre acestea si sa inlocuiasca papucii din camera $a$ cu papucii din camera $b$ si invers. Apoi se va bucura de vizita si va profita de timpul cat schimba papucii punand cat mai multe intrebari ghidului.

h2. Date de intrare

Pe prima linie a fisierului de intrare $papuci.in$ se vor afla $N$ si $K$ cu semnificatiile de mai sus. Pe linia a doua se va afla un sir de $N$ litere mici ale alfabetului englez, astfel incat al $i$-lea caracter sa reprezinte tipul initial de papuci din camera $i$. Pe urmatoarele $26$ de linii se vor afla cate $26$ de numere reprezentand matricea $A$ ({$A[i][j]$} = timpul de care are nevoie Ionel pentru a descalta papucii de tipul $i$ si a incalta papucii de tipul $j$). Pe fiecare din urmatoarele $K$ linii se vor afla cate 2 numere $a$ si $b$, {$a ≤ b$}, reprezentand un schimb de papuci pe care Ionel il poate face intre camerele $a$ si $b$ inainte de a-si incepe vizita.

Pe prima linie a fisierului de intrare $papuci.in$ se vor afla $N$ si $K$, reprezentand numarul de camere ale muzeului, respectiv numarul de schimburi de papuci intre camere. Pe linia a doua se va afla un sir de $N$ litere mici ale alfabetului englez, astfel incat al $i$-lea caracter sa reprezinte tipul initial de papuci din camera $i$. Pe urmatoarele $26$ de linii se vor afla cate $26$ de numere reprezentand matricea $A$ ($A[i][j]$ = timpul de care are nevoie Ionel pentru a descalta papucii de tipul $i$ si a incalta papucii de tipul $j$). Pe fiecare din urmatoarele $K$ linii se va afla cate o pereche de numere $a b$ ($a ≤ b$), despartite printr-un spatiu, reprezentand un schimb posibil de papuci intre camerele $a$ si $b$.

h2. Date de iesire

In fisierul de iesire $papuci.out$ se vor scrie pe prima linie 2 numere $X$ si $Y$ reprezentand timpul maxim obtinut de Ionel la schimbarea papucilor, respectiv numarul de schimburi din cele $K$, necesare obtinerii acestui timp $X$. Pe urmatoarea linie se vor scrie numerele de ordine ale celor $Y$ schimburi folosite de Ionel (schimburile sunt numerotate de la $1$ la $K$ in ordinea in care apar in fisierul de intrare).

In fisierul de iesire $papuci.out$ se vor scrie pe prima linie 2 numere $X$ si $Y$ reprezentand timpul maxim obtinut de Ionel la schimbarea papucilor, respectiv numarul de schimburi intre camere necesare obtinerii acestui timp $X$. Pe urmatoarea linie se vor scrie $Y$ numere distincte intre $1$ si $K$ bla bla bla

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$ schimburi.
* Nu exista doua schimburi $(a,b)$ si $(c,d)$ cu $c > a$, $c < b$ si $b < d$ (altfel spus, perechile nu se intersecteaza)
* Schimburile trecute in fisierul de iesire trebuie sa fie distincte (un schimb nu va fi trecut de mai multe ori).

h2. Exemplu