kafka

Недоволен от тежката работа и ниската заплата, чиновник от кметството на град Безумний, изнамерил оригинален метод за решаване молбите на гражданите: да ги „размотава”, докато те се изморят. Така всеки гражданин, който има проблем и желае да го реши в кметството, трябва да мине през гише информация”, където получава карта с цвят 1 (цветовете са кодирани с последователните цели числа от 1 до nc), върху която е записан номерa bs на офиса, където би трябвало да бъде решен (теоретично) неговият проблем. Офисите са номерирани с последователните цели числа от 1 до nb. Но чиновникът от споменатия офис, естествено счита, че не той трябва да реши молбата и много учтиво дава на гражданина ново картонче в зависимост от цвета на картончето, което вече гражданинът има, като върху новото картонче записва номер на друг офис. Гражданинът отива там и историята се повтаря по подобен начин и в следващия офис, и т.н. Отиването от един офис до друг отнема на гражданина една минута, а издаването на новото картонче е мигновенно. След t минути от напускането на гише информация” гражданинът се изтощава напълно и се отказва от по-нататъшни си опити да реши проблема като си отива у дома.

Задача

При дадени стойности на nb, nc, bs и t, определете номера на офиса, издал последното картонче на гражданина, след което гражданинът си тръгва за дома. За всеки офис е даден цветът на новото картонче, което се издава в офиса и номера на следващия офис, записан върху това картонче.

Вход

Входният файл kafka.in съдържа на първия си ред числата nb, nc, bs и t, разделени с интервали. Всеки от следващите nb*nc реда съдържа по две цели положителни числа, разделени с интервал. Те задават цвета и номера, записан върху картончето, издадено съответно от офис 1,2,...,nb, в зависимост от цвета на донесеното картонче 1,2,...,nc. Т.е., редът от файла с номер (i-1)*nc+j+1 (където 1<=i<=nb и 1<=j<=nc) съдържа цвета и номера на картончето, което е издадено в офис i при цвят j на донесеното картонче.

Изход

Изходният файл kafka.out трябва да съдържа номера на последния посетен офис от гражданина.

Ограничения

Пример

kafka.in

kafka.out

Обяснения

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

1

Първият ред показва, че nb=3, nc=2, bs=2 и t=7.
Вторият ред
задава, че ако гражданинът отиде в офис 1 с цвят 1 на картончето,  ще му бъде дадено картонче с цвят 2, върху което е написан номер 2.

Третият ред задава, че ако гражданинът отиде в офис 1 с цвят 2 на картончето,  ще му бъде дадено картонче с цвят 1, върху което е написан номер 3.

Четвъртият ред задава, че ако гражданинът отиде в офис 2 с цвят 1 на картончето,  ще му бъде дадено картонче с цвят 2, върху което е написан номер 1.

Петият ред задава, че ако гражданинът отиде в офис 2 с цвят 2 на картончето,  ще му бъде дадено картонче с цвят 1, върху което е написан номер 3.

Шестият ред задава, че ако гражданинът отиде в офис 3 с цвят 1 на картончето,  ще му бъде дадено картонче с цвят 1, върху което е написан номер 1.

Седмият ред задава, че ако гражданинът отиде в офис 3 с цвят 2 на картончето,  ще му бъде дадено картонче с цвят 1, върху което е написан номер 2.

Нека тройката (c,b,m) да показва, че гражданинът има картонче с цвят c в офис b и там е m минути след напускане на  гише информация” . Тогава пътят на гражданина е следният:

(1,2,1)->(2,1,2)->(1,3,3)->(1,1,4)->(2,2,5)->(1,3,6)->(1,1,7),

Това показва, че последният посетен офис има номер 1.

 Време за работа на програмата: 0.1 секунди за тест

lect. drd. Radu Boriga
"Titu Maiorescu" University - Bucharest
Contact:r_boriga@yahoo.com

Превод на български: Емил Келеведжиев