Nemultumiti de conditiile grele de munca si de salariile mici, functionarii din primaria orasului Unsinnigburg au gasit o metoda foarte ingenioasa de a rezolva doleantele cetatenilor: tracasarea pana la epuizare. Astfel, orice cetatean care are o problema de rezolvat in primarie trebuie sa treaca mai intai pe la biroul "Informatii" de unde va primi un cartonas colorat cu o culoare 1 (culorile sunt codificate prin numere naturale consecutive cuprinse intre 1 si nc) pe care este scris numarul bs al biroului la care el trebuie sa mearga pentru a-si rezolva (teoretic) problema. Birourile sunt numerotate cu numere naturale consecutive cuprinse intre 1 si nb. Din pacate (dar nu si din intamplare) functionarul din biroul respectiv va constata ca nu el trebuie sa rezolve problema respectiva si, plin de amabilitate, ii va inmana cetateanului, in functie de culoarea cartonasului pe care acesta il are, un alt cartonas, nu neaparat colorat diferit, dar care sigur va avea scris pe el numarul altui birou. Povestea se va repeta si in noul birou, drept care, in scurt timp, cetateanul respectiv va fi suficient de tracasat ca sa nu-si dea seama ca este posibil sa se plimbe, inutil, pe un acelasi traseu. Deplasarea cetateanului de la un birou la altul se face intr-un minut, iar eliberarea unui cartonas nou, in orice birou, este instantanee. Dupa t minute de la plecarea din biroul "Informatii", primind un nou cartonas inutil intr-un birou, cetateanul, epuizat psihic si fizic, va renunta sa mai incerce sa-si rezolve problema si va pleca acasa, lasandu-i pe functionari sa-si bea linistiti cafelele.

Cerinta

Dandu-se valorile nb, nc, bs si t, sa se determine numarul biroului care a eliberat cetateanului ultimul cartonas, inainte ca acesta sa se hotarasca sa renunte. Pentru fiecare birou se cunosc culoarea noului cartonas ce va inmanat cetateanului, precum si numarul noului birou indicat, in functie de fiecare culoare posibila a cartonasului cu care cetateanul s-a prezentat la acel birou.

Date de intrare

Fisierul de intrare kafka.in contine pe prima linie numerele nb, nc, bs si t, despartite prin spatii, iar pe fiecare din urmatoarele nb*nc linii se gasesc cate doua numere naturale, despartite printr-un spatiu, reprezentand culoarea si numarul unui cartonas eliberat de fiecare birou 1,2,...,nb in functie de toate culorile 1,2,...,nc posibile pentru cartonasul cu care cetateanul s-a prezentat la biroul respectiv, astfel: pe linia (i-1)*nc+j+1 din fisier (unde 1<=i<=nb si 1<=j<=nc) sunt scrise culoarea noului cartonas eliberat cetateanului in biroul i si numarul scris pe cartonas in cazul in care cetateanul s-a prezentat la biroul i avand un cartonas de culoare j.

Date de iesire

Fisierul de iesire kafka.out va contine o singura linie pe care va fi scris numarul biroului indicat in cerinta problemei.

Restrictii

• 1 <= nb <= 200
• 1 <= nc <= 20
• 1 <= bs <= 200
• 1 <= t <= 1000000000

Exemplu

lect. drd. Radu Boriga
Universitatea "Titu Maiorescu" - Bucuresti
Contact:r_boriga@yahoo.com