¡El granjero John lleva a Bessie y a las vacas de crucero! Navegan por una red de ríos con ~N~ puertos numerados del ~1~ al ~N~, y Bessie comienza en el puerto ~1~. Cada puerto tiene exactamente dos ríos que salen de él, los cuales llevan directamente a otros puertos, y solo se puede navegar en una dirección.

En cada puerto, los guías turísticos eligen el río de la izquierda o el de la derecha para navegar a continuación, pero repiten las mismas elecciones una y otra vez. Más concretamente, los guías turísticos han elegido una secuencia corta de ~M~ direcciones, cada una de ellas "izquierda" o "derecha", y la han repetido ~K~ veces. Bessie cree que está dando vueltas en círculos. ¡Ayúdala a descubrir dónde termina!

Entrada

• Línea 1: Tres números enteros separados por espacios: ~N, M~ y ~K~.
• Líneas 2 a N+1: La línea i+1 contiene dos números enteros separados por espacios, que representan el número de puertos a los que conducen los ríos izquierdo y derecho del puerto ~i~, respectivamente.
• Línea N+2: ~M~ caracteres separados por espacios, 'L' o 'R'. 'L' representa la opción 'izquierda' y 'R' representa la opción 'derecha'.

Salida

Un número entero que indica el número del puerto donde termina el crucero de Bessie.

Restricciones

• ~1 \leq N \leq 1000~
• ~1 \leq M \leq 500~
• ~1 \leq K \leq 1,000,000,000~

Ejemplo de Entrada

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

Detalles de la Entrada: Los números de puerto están dispuestos en sentido horario en un círculo, donde 'L' representa una rotación en sentido horario y 'R' una rotación en sentido antihorario. La secuencia tomada es ~LLRLLRLLR~.

Ejemplo de Salida

4

Detalles de la Salida: Tras la primera iteración de la secuencia de direcciones, Bessie se encuentra en el puerto ~2~ ~(1 \rightarrow 2 \rightarrow 3 \rightarrow 2)~; tras la segunda, está en el puerto ~3~ ~(2 \rightarrow 3 \rightarrow 4 \rightarrow 3)~, y al final se encuentra en el puerto ~4~ ~(3 \rightarrow 4 \rightarrow 1 \rightarrow 4)~.

USACO 2013 US Open, Silver. Problem 3. Luxury River Cruise.