kafka

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

Exemplu

kafka.in

 kafka.out

Explicatie

3 2 2 7
2 2
1 3
2 1
1 3
1 1
1 2

1

Din prima linie a fisierului de intrare rezulta ca nb=3, nc=2, bs=2 si t=7.
Din a doua linie rezulta ca un cetatean care a venit la biroul 1 cu un cartonas avand culoarea 1 va fi trimis cu un cartonas avand culoarea 2 spre biroul 2, iar din a treia linie deducem ca daca el a venit la biroul 1 cu un cartonas avand culoarea 2 va fi trimis cu un cartonas avand culoarea 1 spre biroul 3.
Din a patra linie rezulta ca un cetatean care a venit la biroul 2 cu un cartonas avand culoarea 1 va fi trimis cu un cartonas avand culoarea 2 spre biroul 1, iar din a cincea linie deducem ca daca el a venit la biroul 2 cu un cartonas avand culoarea 2 va fi trimis cu un cartonas avand culoarea 1 spre biroul 3.
Din a sasea linie rezulta ca un cetatean care a venit la biroul 3 cu un cartonas avand culoarea 1 va fi trimis cu un cartonas avand culoarea 1 spre biroul 1, iar din a saptea linie deducem ca daca el a venit la biroul 3 cu un cartonas avand culoarea 2 va fi trimis cu un cartonas avand culoarea 1 spre biroul 2.
In continuare, printr-un triplet (c,b,m) vom intelege ca respectivul cetatean s-a prezentat cu un cartonas avand culoarea c la biroul b dupa m minute de la plecarea din biroul "Informatii". Astfel, traseul urmat de cetatean in acest caz a fost urmatorul: (1,2,1)->(2,1,2)->(1,3,3)->(1,1,4)->(2,2,5)->(1,3,6)->(1,1,7), deci ultimul birou vizitat de el inainte sa renunte a fost biroul 1.

 Timp maxim de executie/test: 0.1 secunde

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