Luxury River Cruise

Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with $N$ ports ($1 \le N \le 1000$) labeled $1 \dots N$, and Bessie starts at port $1$. Each port has exactly two rivers leading out of it, going directly to two other ports, and each river can be sailed in only one direction.

At each port the tour guides pick either the left river or the right river to sail down next, and they repeat the same pattern over and over. Concretely, the guides fix a short sequence of $M$ directions ($1 \le M \le 500$), each either left or right, and they follow this whole sequence $K$ times ($1 \le K \le 10^9$). Bessie feels like she is going in circles -- help her work out which port she finishes at!

• Line 1: three space-separated integers $N$, $M$, and $K$.
• Lines 2 to $N+1$: line $i+1$ contains two space-separated integers -- the ports that port $i$'s left river and right river lead to, respectively.
• Line $N+2$: $M$ space-separated characters, each either L or R. L means the left river and R means the right river.

• A single integer: the number of the port where Bessie's cruise ends.

In the sample, the port numbers are arranged clockwise around a circle, L is a clockwise step and R is a counterclockwise step, and the sequence followed is L L R repeated three times.

After the first full pass through the direction sequence Bessie is at port $2$ ($1 \to 2 \to 3 \to 2$); after the second pass she is at port $3$ ($2 \to 3 \to 4 \to 3$); and after the third pass she finishes at port $4$ ($3 \to 4 \to 1 \to 4$).