设 $K$ 为某个正整数。我们有一条包含 $N=2^K$ 个格子的纸带。格子从左到右依次编号为 $1$ 到 $N$。以下是 $K=3$ 且相应地 $N=8$ 时纸带最初的样子（这是侧视图，而不是俯视图！）：

1 2 3 4 5 6 7 8

我们可以按以下方式折叠纸带：在纸带的中心进行标记，保持一半不动，将另一半向上或向下折叠。首先，我们将右半部分向上折叠。然后，我们将左半部分向下折叠，最后，我们将左半部分向上折叠。以下是样例纸带在每一步折叠后的样子：

8 7 6 5          6 5          7
1 2 3 4    →     3 4    →     2
                 2 1          3
                 7 8          6
                              5
                              4
                              1
                              8

正如我们所见，折叠后纸带上的数字从上到下的顺序为：7, 2, 3, 6, 5, 4, 1, 8。

这就是我们需要解决的问题。在本题中，$K$ 是固定的且等于 $21$。因此，我们有一条包含 $2^{21}$ 个格子的纸带；这条纸带根据一系列折叠指令被折叠了 $21$ 次。折叠指令包括：

• LU（将左半部分向上折叠）
• LD（将左半部分向下折叠）
• RU（将右半部分向上折叠）
• RD（将右半部分向下折叠）

我们需要确定折叠后纸带上数字的顺序。更具体地说，我们需要知道前 1024 个数字——它们应该在输出中呈现。

输入格式

输入文件包含折叠指令，共 21 行。每行包含两个字符：LU、LD、RU 或 RD。第 $M$ 行包含第 $M$ 次（$1 \le M \le 21$）折叠的描述。

输出格式

输出共包含 1024 行。第 $M$ 行（$1 \le M \le 1024$）包含从上往下数第 $M$ 个数字。

样例

样例输入 1

RU
LD
LU

样例输出 1

7
2
3
6
5

说明

样例数据对于在纸上展示来说太大了，但如果 $K=3$ 且你需要输出前 5 个数字，则输出如上所示。