树上游⾛

题目描述

⼩杨有⼀棵包含⽆穷节点的⼆叉树（即每个节点都有左⼉⼦节点和右⼉⼦节点；除根节点外，每个节点都有⽗节 点），其中根节点的编号为 ，对于节点 ，其左⼉⼦的编号为 ，右⼉⼦的编号为 。 ⼩杨会从节点 开始在⼆叉树上移动，每次移动为以下三种移动⽅式的任意⼀种： 第1种移动⽅式： 如果当前节点存在⽗亲节点，向上移动到当前节点的⽗亲节点，否则不移动； 第2种移动⽅式： 移动到当前节点的左⼉⼦； 第3种移动⽅式： 移动到当前节点的右⼉⼦。 ⼩杨想知道移动 次后⾃⼰所处的节点编号。数据保证最后的所处的节点编号不超过 。

输入格式

第⼀⾏包含⼀个正整数 ，代表移动次数和初始节点编号。 第⼆⾏包含⼀个长度为 且仅包含⼤写字母 的字符串，代表每次移动的⽅式，其中 代表第1种移动⽅式， 代表第2种移动⽅式， 代表第3种移动⽅式。

输出格式

输出⼀个正整数，代表最后所处的节点编号。

样例输入 #1

1 3 2
2 URR
1 7

样例输出 #1

样例解释 #1

⼩杨的移动路线为 2-1-3-7。 子任务编号 数据点占比 1 20% 2 20% 3 60% 对于全部数据，保证有 。

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。