kafka

Disgruntled by the hard work conditions and low wages, the clerks working in Unsinnigburg City Hall have found a very ingenious method of solving their citizens requests: irritating them until they are exhausted. As such, any citizen that has a problem he wishes to solve at City Hall must first pass via the "Information" desk, where he will receive a card color 1 (the colors are encoded using consecutive positive integers between 1 and nc) which contains number bs of the office to whom he should go to solve his problem (theoretically). The offices are numbered using consecutive positive integers between 1 and nb. Unfortunately (but not accidentally), the clerk from said office will realize that it is not he that has to solve said problem and, very courteously, will hand the citizen, depending on the color of the card he already has, another card, not necessarily a different color, but which will certainly have the number of a different office on it. The story will repeat itself in the new office therefore, in a brief while, that citizen will be irritated enough not to realize that it is possible he will again be walking, uselessly, on the same route. The citizen's moving from one office to the next takes a minute, and the issuing of a new card, in any office, is instantaneous. t minutes after leaving the "Information" desk, and after receiving a new useless card in an office, the citizen, mentally and physically exhausted, will give up trying to solve his problem and will go home, leaving the clerks to drink their coffee in peace.

Task

Being given values nb, nc, bs and t, determine the number of the office that issued the last card to the citizen before he decided to quit. For each office we know the color of the new card that will be handed to the citizen, as well as the number of the new office indicated on it, depending on each possible color of the card with which the citizen presented himself to that office.

Input Data

Input file kafka.in contains on line one numbers nb, nc, bs and t, separated by spaces, and each of the following nb*nc lines contains two positive integers, separated by a space, representing the color and number of a card issued by each office, 1,2,...,nb, depending on all colors 1,2,...,nc possible for the card with which the citizen presented himself to that office, as follows: line (i-1)*nc+j+1 of the file (where 1<=i<=nb and 1<=j<=nc) contains the color of the card issued to the citizen in office i and the number on the card if the citizen presented himself to office i having a card color j.

Output Data

Output file kafka.out will contain a single line which will have the number of the office indicated in the problem task.

Restrictions

Example

kafka.in

 kafka.out

Explanation

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

1

Line one of the input file shows that nb=3, nc=2, bs=2 and t=7.
Line two shows that a citizen who came to office 1 with a card color 1 will be sent with a card color 2 to office 2 and line three shows that if he came to office 1 with a card color 2 he will be sent with a card color 1 to office 3.
Line four shows that a citizen who came to office 2 with a card color 1 will be sent with a card color 2 to office 1 and line five shows that if he came to office 2 with a card color 2 he will be sent with a card color 1 to office 3.
Line six shows that a citizen who came to office 3 with a card color 1 will be sent with a card color 1 to office 1 and line seven shows that if he came to office 3 with a card color 2 he will be sent with a card color 1 to office 2.
From here on the term triplet (c,b,m) will tell us that said citizen presented himself with a card color c at office b m minutes after leaving the "Information" desk. As such, the route followed by a citizen in this case was as follows: (1,2,1)->(2,1,2)->(1,3,3)->(1,1,4)->(2,2,5)->(1,3,6)->(1,1,7), so the last office visited by him before giving up was office 1.

 Time limit: 0.1 seconds/test

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