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

题目描述

徐老师最近在玩一个跑图游戏，这个游戏的地图永远是随机生成的，没有固定且没有边界（无限大）

徐老师控制的人物一开始会处在坐标 $(0,0)$ 的位置上

每次徐老师可以下达一个指令，指令一共有四种：

• U：向上移动一格，假设人物当前坐标为 $(x, y)$，则移动到 $(x - 1, y)$。
• D：向下移动一格，假设人物当前坐标为 $(x, y)$，则移动到 $(x + 1, y)$。
• R：向右移动一格，假设人物当前坐标为 $(x, y)$，则移动到 $(x, y + 1)$。
• L：向左移动一格，假设人物当前坐标为 $(x, y)$，则移动到 $(x, y - 1)$。

而在这个地图生成时，有一部分位置是 空地，有一部分位置是 石头

人物可以移动到空地上，而不能移动到石头上，如果当前指令要求人物走到石头的位置，则这次移动失败，忽略这条指令

例如如下地图，用 $.$ 表示空地，$x$ 表示石头，左上角为 $(0,0)$

.x.
...
...

徐老师输入指令 $RDR$ 后，人物会依次执行以下步骤：

1. R 操作要求往右，但是右侧是石头，无法移动，则忽略这条指令
2. D 操作要求往下，下方是空地，则移动到 $(1,0)$
3. R 操作要求往右，右侧是空地，则移动到 $(1,1)$

最终在这个地图上执行 $RDR$ 指令后，人物会停留在 $(1,1)$ 处

而现在徐老师已经想好了自己要输入的指令 $S$，但是他不知道游戏会生成什么样的地图

他想知道在随机生成的所有地图里，人物最终停留的坐标可能有哪些？

输入格式

输入第一行包含一个整数 $n$ 表示指令的长度

输入第二行包含一个长度为 $n$ 的字符串 $S$ 表示徐老师会输入的指令，保证字符串中只会出现 UDRL 四个字符

输出格式

输出第一行包含一个整数 $m$ 表示人物最终可能停留的坐标数量

接下来 $m$ 行，每行包含两个整数 $x,y$ 最终可能停留的一个坐标

其中所有坐标按 $x$ 从小到大输出，如果 $x$ 相同则按 $y$ 从小到大输出

数据范围

样例输入1

2
DR

样例输出1

4
0 0
0 1
1 0
1 1

样例解释1

操作指令是先向下再向右，所以会涉及到至少 $2 * 2$ 大小的地图，也就是一共可能有 $2^4$ 种地图情况

其中有四种情况决定了终点位置：

(1)如果地图没有石头，则执行后人物会到达 $(1,1)$ (2)如果 $(1,0)$ 有石头，$(0,1)$ 没有石头，则执行后人物会到达 $(0,1)$ (3)如果 $(1,0)$ 没有石头，$(0,1)$ 有石头，则执行后人物会到达 $(1,0)$ (4)如果 $(1,0),(0,1)$ 都有石头，则执行后人物会到达 $(0,0)$

一共四种不同的终点