Cruise on the River Network

Farmer John is taking Bessie and the cows on a cruise through a network of rivers! There are N ports (numbered from 1 to N) and each port has exactly two one‐way rivers leading out of it: one labeled left and the other labeled right. Bessie starts her journey at port 1.

The tour guides have decided on a sequence of M directions (each being either left or right) which is repeated K times. At each port, Bessie sails down the river according to the current direction in the sequence. Your task is to determine the final port at which Bessie will arrive after following the complete sequence of moves.

Formally, let the ports be numbered 1 through N. For each port i, two integers are given: the destination port if the left river is chosen and the destination port if the right river is chosen. A single cycle consists of M moves and the entire journey consists of K such cycles, i.e., a total of M \times K moves. Since K can be very large, you may need to use fast exponentiation (doubling) to compute the result efficiently.

The transition function for one complete cycle can be defined as:

\[ f(i)= \text{port reached from port } i \text{ after performing the sequence of M moves} \]

Then the final answer is:

\[ \text{answer} = f^{K}(1) \]

inputFormat

The input begins with a line containing three integers: N (1 ≤ N ≤ 1000), M (1 ≤ M ≤ 500), and K (1 ≤ K ≤ 10^9).

Then follow N lines, each containing two integers. The i-th line (1-indexed) contains two integers, representing the destination ports if the left or right river is taken from port i.

The last line contains M strings, each either left or right, representing the sequence of directions to be followed (this sequence is repeated K times).

outputFormat

Output a single integer representing the final port number where Bessie ends up.

sample

4 3 1
2 3
3 4
4 1
1 2
left right left

1

</p>