题目描述

你有一个机器人在无限大的平面上走，初始位置为 $(0,0)$ 。

你向它发送了若干个指令，每个指令是 LRUD 之一。如果机器人原来的位置是 $(x,y)$ ，那么四条指令分别会使其移动到 $(x-1,y),(x+1,y),(x,y+1),(x,y-1)$ 。

平面上可能有若干个障碍，但你不知道它们的具体位置。当机器人尝试移动时，它会先判断目标位置是否有障碍，如果存在障碍就会忽略这条指令。

给定长度为 $n$ 的指令序列，求出机器人在执行完这 $n$ 条指令之后可能会在哪些位置。

输入格式

第一行一个正整数 $n$ 。

第二行一个长度为 $n$ 的字符串，由 LURD 组成，表示操作序列。

输出格式

第一行一个正整数 $k$ ，表示可能的位置个数。

接下来 $k$ 行，每行两个整数 $x_i,y_i$ ，表示一个可能的位置。你需要把所有位置以 $x$ 为第一关键字、$y$ 为第二关键字从小到大排序后输出。

样例

样例输入 1

2
RU

样例输出 1

4
0 0
0 1
1 0
1 1

样例解释 1

一组可能的状态是在 $(1,0)$ 有障碍而 $(0,1)$ 没有，那么机器人会忽略第一条指令，然后执行第二条指令，来到 $(0,1)$ 。

样例输入 2

4
LRUD

样例输出 2

4
0 -1
0 0
1 -1
1 0

数据范围

对于 $20\%$ 的数据，保证 $1\le n\le 2$ 。

对于 $40\%$ 的数据，保证 $1\le n\le 4$ 。

对于所有数据，保证 $1\le n\le 20$ 。