题目描述

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

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

输入格式

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

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

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

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

输出格式

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

样例

输入样例

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

输出样例

4

提示

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

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