题目描述

农夫约翰正带着贝西和奶牛们进行一场游船之旅！他们航行在一个拥有 $N$ 个港口（ $1 \le N \le 1000$）的河流网络上，港口编号为 $1$ 到 $N$，贝西从 $1$ 号港口出发。每个港口都有两条流出河流分别通向其他港口，且河流均为单向通行。

在每个港口，导游会选择"左"或"右"方向的河流继续航行，但他们会持续重复相同的选择模式。具体而言，导游选择了一个包含 $M$ 个方向（ $1 \le M \le 500$）的短序列（每个方向不是"左"就是"右"），并将该序列重复 $K$ 次（$1 \le K \le 10^9$）。贝西觉得自己一直在绕圈——请帮助她计算出最终抵达的港口！

输入格式

第1行：输入 $N,M,K$

接下来 $N$ 行，每 $i(1 \le i \le N)$ 行输入两个整数 $x, y$，表示 $i$ 港口的左边和右边分别和 $x, y$ 港口连接。

最后一行：输入 $M$ 个用空格隔开的字符，只由 L 或 R

输出格式

输出一个整数，表示最后 Bessie 停在哪个港口。

输入输出样例 #1

输入 #1

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

输出 #1

4

说明/提示

第一轮的过程为 (1 -> 2 -> 3 -> 2);

第二轮的过程为 (2 -> 3 -> 4 -> 3);

第三轮的过程为 (3 -> 4 -> 1 -> 4);