题目描述

农民约翰带着$\red{Bessie}$和奶牛在邮轮上！他们在网格上的$\red{N}$条河流航行$\red{（1≤}$$\red{N≤}$$\red{1000）}$标记为$\red{1}$到$\red{N，}$一开始他们在开始在河口$\red{1}$。每一个港口都有 两条河流直通，直接通往其他港口，河流只能通过一条路航行。

在每一个港口，导游选择左边的河或右边的河向下航行，但他们不断重复相同的选择一遍又一遍。更具体地说，导游选择了一个$\red{m}$方向$\red{（1 < =m= 500）}$，每一个向左或向右，并重复它$\red{K}$次$\red{（1 < = K = 1000000000）}$。$\red{Bessie}$认为她是在兜圈子，帮她找出结束的位置！

输入格式

第 $\red{1 }$行：三个空格分隔的整数 $\red{N}$、$\red{M }$和 $\red{K}$。

第 $\red{2..N+1 }$行：第 $\red{i+1 }$行有两个空格分隔的整数，

表示港口 $\red{i }$的左右河流分别通向的港口数量。

第 $\red{N+2 }$行：$\red{M }$个空格分隔的字符，"$\red{L}$"或"$\red{R}$"。"$\red{L}$"代表选择"左"，"$\red{R}$"代表选择"右"。

输出格式

第 $\red{1 }$行：一个整数，给出 $\red{Bessie }$航行结束的港口编号。

样例

输入样例

4 3 3 
2 4 
3 1 
4 2 
1 3 
LLR

输出样例

4

提示

端口号按顺时针方向排列成一个圆圈，"$\red{L}$"为顺时针旋转，"$\red{R}$"为逆时针旋转。采用的序列是 $\red{LLRLLRLLR}$。

在方向序列的第一次迭代之后，$\red{Bessie }$在端口 $\red{2 (1 -> 2 -> 3 -> 2)}$；在第二个之后，她在端口 $\red{3 (2 -> 3 -> 4 -> 3)，}$最后她在端口 $\red{4 (3 -> 4 -> 1 -> 4)}$