该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P4 折纸

题目描述

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
DR

2 U

2
DRUR

11 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 \le 8$。
• 对于 $100\%$ 的数据，满足 $1 \le n \le 15$。