Description

Farmer John is taking Bessie and the other cows on a cruise! They are sailing on a river network with $N$ ports ($1 \le N \le 10^3$), numbered $1, 2, 3, \dots, N$, and Bessie starts at port $1$. Each port has exactly two outgoing rivers that lead directly to other ports, and these rivers can be traversed only in one direction.

At each port, the guide chooses to take the left river or the right river to continue downstream, and they repeat the same sequence of choices over and over. More specifically, the guide has fixed in advance a direction sequence of length $M$ ($1 \le M \le 500$), each direction being either left or right, and then repeats this sequence $K$ times ($1 \le K \le 10^9$). Please help compute the port where Bessie finally stops.

Input Format

Line $1$: Three space-separated integers $N$, $M$, $K$.

Lines $2$ to $N+1$: Line $i+1$ contains two space-separated integers, the indices of the ports reached by taking the left and right rivers from port $i$.

Line $N+2$: $M$ space-separated characters, each either L or R. L means take the left river, and R means take the right river.

Output Format

Output a single integer, the index of the port where Bessie’s cruise ends.

4 3 3 
2 4 
3 1 
4 2 
1 3 
L L R 

4 

Hint

In the sample, after finishing the first pass of the direction sequence, Bessie arrives at port $2$ (path: $1 \to 2 \to 3 \to 2$)；
after the second pass, she arrives at port $3$ (path: $2 \to 3 \to 4 \to 3$)；
finally, she ends at port $4$ (path: $3 \to 4 \to 1 \to 4$).

Thanks to

Translated by ChatGPT 5