### 问题描述 小齐和她的牛儿们决定进行一次豪华河流之旅！她们将在一个有 $ N $ 个港口（$ 1 \leq N \leq 1,000 $）的河流网络中航行，而小齐将从港口 $1$ 出发。每个港口都有两条直接通往其他港口的河流，而且河流只能单向航行。 在每个港口，导游们选择要么沿着“左”河流，要么沿着“右”河流航行，但他们一直重复相同的选择。更具体地说，导游们选择了一个短序列 $ M $ 个方向（$ 1 \leq M \leq 500 $），每个方向要么是“左”，要么是“右”，并且将其重复 $ K $ 次（$ 1 \leq K \leq 1,000,000,000 $）。小齐觉得她一直在绕圈子，帮助她找出最终停靠的地方吧。 ### 输入格式 第 $1$ 行：三个用空格分隔的整数 $ N, M, K $。 第 $2$ 行至第 $1+N $行：第 $ i $ 行有两个用空格分隔的整数，表示港口 $ i $ 的左右两条河流通往的港口号。 第 $1+N$ 行后：$ M $ 个由空格分隔的字符，每个字符要么是 $L$ 表示“左”，要么是 $R$ 表示“右”。 ### 输出格式 一个整数，表示小齐最终停靠的港口号。 ### 样例输入 ``` 4 3 3 2 4 3 1 4 2 1 3 L L R ``` ### 样例输出 ``` 4 ``` ### 评测数据规模 $1 \leq N, M \leq 1,000$，$1 \leq K \leq 1,000,000,000$。