题目描述

农民约翰正带着贝西和其他奶牛们进行一次巡航！他们航行在一个有 $N$ 个港口（$1 \le N\le10^3$）的河网中，港口编号为 $1,2,3\dots N$，贝西从港口 $1$ 出发。每个港口恰好有两条流出的河道，直接通向其他港口，并且这些河道只能单向航行。

在每个港口，导游会选择走左边的河道或右边的河道继续向下游航行，但他们会一遍又一遍地重复相同的选择顺序。更具体地说，导游事先选定了一个长度为 $M$ 的方向序列（$1\le M\le500$），每个方向要么是左，要么是右，然后将这个序列重复 $K$ 次（$1\le k\le10^9$），请帮她计算出她最终会停在哪个港口。

输入格式

第 $1$ 行：三个用空格隔开的整数 $N,M,K$。

第 $2$ 行到第 $N+1$ 行中，第 $i+1$ 行包含两个用空格隔开的整数，分别表示港口 $i$ 的左边河道和右边河道通向的港口编号。

第 $N+2$ 行：M 个用空格隔开的字符，每个字符是 L 或 R。L 表示选择左边的河道，R 表示选择右边的河道。

输出格式

输出一个整数，表示贝西的巡航最终停靠的港口编号。

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

4 

提示

样例中在执行完第一遍方向序列后，贝西到达港口 $2$（路径：$1 \to 2 \to 3 \to 2$）；

第二遍结束后，她到达港口 $3$（路径：$2 \to 3 \to 4 \to 3$）；

最终结束时，她到达港口 $4$（路径：$3 \to 4 \to 1 \to 4$）。

感谢