Dr. X 拿出了一张正方形纸，将其划分成 2^n \times 2^n 个大小相等的小格子。纸有正、反两面：初始时，纸正面朝上。Dr. X 将会按照指定的顺序折叠这张纸，每次折叠，都沿中线将纸对折，共分四种方向，如图所示：

• D (Down): 上半部分向下折，盖在下半部分上。
• U (Up)：下半部分向上折，盖在上半部分上。
• R (Right)：左半部分向右折，盖在右半部分上。
• L (Left)：右半部分向左折，盖在左半部分上。

对折时，被翻折的部分会整体翻转（被翻折的部分正面和反面互换，且原本在最底层的格子折叠后会翻到最上层），翻转后的部分作为一个整体，叠加到另一半的上方。经过 2n 次折叠后，纸最终被折成一个 1 \times 1 的方块，由 2^{2n} 层格子叠成。Dr. X 想知道：初始时位于左上角 (1,1) 的那个格子，最终在方块中的第几层（从上往下数，最上面一层为第 1 层），以及它的正面是朝上还是朝下。

输入共两行。第一行一个正整数 n，表示纸张的边长为 2^n。第二行一个由 D、U、R、L 组成的字符串，长度为 2n，描述折叠的顺序。保证其中恰好包含 n 个纵向折叠（D 或 U）和 n 个横向折叠（R 或 L）。

输出两个值，用空格分隔：第一个是一个整数，表示左上角格子从上往下数所在的层数；第二个是一个字符，U 表示正面朝上，D 表示正面朝下。

样例1解释

• 初始纸张为 2 \times 2。四个格子分别为 (1,1)、(1,2)、(2,1)、(2,2)，全部正面朝上。
• 第 1 次 D：上半部分 (1,1) 和 (1,2) 向下折，盖在下半部分上。折叠后纸变为 1 \times 2 两层：
  • 左列从上到下：(1,1) 朝下、(2,1) 朝上。
  • 右列从上到下：(1,2) 朝下、(2,2) 朝上。
• 第 2 次 R：左列向右折，盖在右列上（每层翻转）。折叠后纸变为 1 \times 1，共 4 层，从上到下依次为：(2,1) 朝下、(1,1) 朝上、(1,2) 朝下、(2,2) 朝上。

数据规模

• 对于 40\% 的数据，满足 n \leq 8。
• 对于 100\% 的数据，满足 1 \leq n \leq 15。

2026年江苏省＂信息与未来＂小学生编程

江苏省赛2026