你正在开发一种月球探测机器人。现在，该机器人正在一个大型场地中进行实验。

该场地可以看作是一个无限的二维平面。最初，机器人位于 $(0, 0)$。随后，它将依次执行 $n$ 条指令。每条指令可以用一个大写英文字母表示：

• “L”：从 $(x, y)$ 移动到 $(x - 1, y)$。
• “R”：从 $(x, y)$ 移动到 $(x + 1, y)$。
• “D”：从 $(x, y)$ 移动到 $(x, y - 1)$。
• “U”：从 $(x, y)$ 移动到 $(x, y + 1)$。

注意，除了原点 $(0, 0)$ 外，场地上还存在一些障碍物。当机器人尝试移动到下一个位置时，它会检查目标坐标处是否有障碍物。如果存在障碍物，机器人将停留在当前位置，并将当前指令标记为已执行，然后继续执行后续指令。

你已经向机器人发送了 $n$ 条指令，但不幸的是，由于一些故障，场地的地图和机器人的位置无法传输给你。假设机器人已经执行完了所有 $n$ 条指令。在前往场地之前，你想知道你可能会在哪些位置找到机器人。请编写一个程序，找出机器人最终可能位于的所有位置。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 20$)，表示指令的数量。 第二行包含一个长度为 $n$ 的字符串 $s$ ($s_i \in \{“L”, “R”, “D”, “U”\}$)，其中第 $i$ 个字母表示发送给机器人的第 $i$ 条指令。

输出格式

首先输出一行，包含一个整数 $k$，表示可能的位置数量。然后输出 $k$ 行，每行包含两个整数 $x$ 和 $y$，表示机器人最终可能位于 $(x, y)$。当 $k \ge 2$ 时，你应该按照 $x$ 的升序输出答案，若 $x$ 相等，则按照 $y$ 的升序输出。

样例

样例输入 1

2
RU

样例输出 1

4
0 0
0 1
1 0
1 1

样例输入 2

4
LRUD

样例输出 2

4
0 -1
0 0
1 -1
1 0