În oraşul Ababuribu există o porţiune de şosea specială de formă dreptunghiulară. Şoseaua este formată din m rânduri a câte n dale pătrate de aceeaşi dimensiune. Dalele sunt însă colorate în n culori diferite, codificate prin numere întregi cuprinse între 1 şi n. Se ştie că pentru fiecare culoare există exact m dale colorate cu aceea culoare.
Coordonatele dalelor vor fi date de linia şi coloana pe care se găseşte dala, numerotarea rândurilor făcându-se de sus în jos începând cu 1, iar coloanele se numerotează de la stânga la dreapta începând cu 1.
Primarul oraşului doreşte să construiască o trecere de pietoni pe această porţiune de şosea. O trecere va fi formată din m dale având toate aceeaşi culoare şi aflate vertical una sub alta, de la primul până la ultimul rând. Astfel dalele care vor forma trecerea vor avea coordonatele de forma (1,c), (2,c), (3,c),..., (m,c), unde c este coloana pe care este construită trecerea.
Pentru a construi trecerea, primarul dă voie constructorilor să aleagă culoarea (din cele n disponibile) pe care o va avea trecerea de pietoni precum şi coloana pe care se va construi trecerea. De asemenea constructorii au voie să schimbe între ele dalele de pe şosea, însă efortul total va trebui să fie cât mai mic posibil. Efortul schimbării între ele a două dale de coordonatele (x,y) şi respectiv (x1,y1) este egal cu |x-x1|+|y-y1|, unde prin |a| s-a notat valoarea absolută a valorii a.
De exemplu pentru şoseaua din figura alăturată, cea mai eficientă soluţie este construirea unei treceri de culoare 1, pe coloana 6.
Efortul construirii acestei şosele este 5. Se vor efectua următoarele schimbări: dala (1,6) cu dala (1,7), dala (2,5) cu dala (3,6), dala (3,7) cu dala (4,6).
Dacă există mai multe soluţii care implică acelaşi efort minim, primarul preferă acea culoare având cel mai mic cod, iar dacă pentru această culoare se pot construi cu acelaşi efort minim, mai multe treceri, el va prefera cea mai din stânga trecere.
Cerinţă
Fiind date dimensiunile m şi n ale şoselei şi culorile celor mxn dale, se cere să determinaţi efortul necesar construirii treceri de pietoni, culoarea pe care o va avea această trecere, precum şi coloana pe care va fi construită trecerea.
Date de intrare
Fişierul de intrare trecere.in conţine pe prima linie două numere naturale m şi n separate printr-un spaţiu, reprezentând numărul de linii respectiv de coloane ale şoselei. Următoarele m linii ale fişierului vor conţine câte n numere naturale cuprinse între 1 şi n (inclusiv) separate prin câte un spaţiu, reprezentând culorile dalelor de pe şosea.
Date de ieşire
Fişierul de ieşire trecere.out va conţine pe prima sa linie trei numere întregi a, b şi c, separate prin câte un spaţiu, având următoarea semnificaţie: a – efortul depus pentru construirea trecerii de pietoni, b - culoarea trecerii de pietoni iar c – coloana pe care se construieşte trecerea.
Restricţii
1 <= m, n <= 120
Pentru valoarea corectă a efortului depus se acordă 30% din punctaj.
