호화 강 유람선

농부 존(Farmer John)이 베시(Bessie)와 소들을 데리고 유람선 여행을 떠납니다! 이들은 $1$번부터 $N$번까지 번호가 붙은 $N$개의 항구($1 \le N \le 1000$)로 이루어진 강 네트워크를 항해하며, 베시는 $1$번 항구에서 출발합니다. 각 항구에서는 정확히 두 개의 강이 흘러 나가 서로 다른 두 항구로 곧장 이어지고, 각 강은 한 방향으로만 항해할 수 있습니다.

각 항구에서 안내원은 다음으로 내려갈 강으로 왼쪽 강 또는 오른쪽 강을 고르며, 같은 선택 패턴을 계속 반복합니다. 구체적으로, 안내원은 각각 왼쪽 또는 오른쪽을 뜻하는 방향 $M$개로 이루어진 짧은 순서열($1 \le M \le 500$)을 정해 두고, 이 순서열 전체를 $K$번($1 \le K \le 10^9$) 반복합니다. 베시는 자신이 제자리를 맴돌고 있는 것 같다고 느낍니다. 베시가 어느 항구에서 여행을 마치는지 알아내는 것을 도와주세요!

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $M$, $K$.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 두 정수가 공백으로 구분되어 주어지며, 각각 $i$번 항구의 왼쪽 강과 오른쪽 강이 이어지는 항구의 번호입니다.
• $N+2$째 줄: 각각 L 또는 R인 문자 $M$개가 공백으로 구분되어 주어집니다. L은 왼쪽 강을, R은 오른쪽 강을 뜻합니다.

• 베시의 유람선 여행이 끝나는 항구의 번호를 나타내는 정수 하나.

예시에서 항구 번호는 원을 따라 시계 방향으로 배치되어 있으며, L은 시계 방향으로 한 칸, R은 반시계 방향으로 한 칸 이동하는 것에 해당하고, 따르는 순서열은 L L R을 세 번 반복한 것입니다.

방향 순서열을 첫 번째로 모두 따르고 나면 베시는 $2$번 항구에 있고($1 \to 2 \to 3 \to 2$), 두 번째로 따르고 나면 $3$번 항구에 있으며($2 \to 3 \to 4 \to 3$), 세 번째로 따르고 나면 $4$번 항구에서 여행을 마칩니다($3 \to 4 \to 1 \to 4$).