题目描述

在一个无限大的二维平面网格地图上，存在两类地形：空地（可通行）和石头（不可通行）。一开始，角色位于坐标 (0, 0)，该点固定为空地。 现给定一个移动指令序列 S，仅包含 'W', 'A', 'S', 'D'，假设角色原先坐标为(x,y),移动规则如下:

'W':向上移动一格至(x-1,y)。

'A':向左移动一格至(x,y-1)。

'S':向下移动一格至(x+1,y)。

'D':向右移动一格至(x,y+1)。

角色可以移动至空地，但不能移动至石头上，因此如果移动指令会使角色移动到石头的位置，那角色就会忽略这条指令。

例如对于这个地图，用O表示空地，X表示石头，左上角为(0,0)：

OXO

OOO

OOO

那么对于移动序列DSD：

1.D要求往右，但右侧是石头无法移动，忽略这次指令。

2.S要求往下，下方是空地，移动到(1,0)

3.D要求往右，右侧是空地，移动到(1,1)

最终角色会停留在(1,1)处。

现在已知一个确定的操作序列S，但地图的生成是随机的，除了初始位置之外，其他位置都可能是空地或者石头。想知道，在所有可能的地图里，角色最终停留的位置可能有哪些？

输入格式

输入第一行包含一个整数N表示移动序列的长度。 输入第二行包含一个长度为N的字符串S表示给定的移动序列，保证序列只包含WASD四种指令。

输出格式

输出第一行包含一个整数K表示角色最终可能停留的坐标数量。 接下来K行，每行包含空格分隔的两个整数x,y表示一个角色最终可能停留的坐标。 其中所有坐标按x升序输出，如果x相同的按y升序输出。

样例数据

2
SD

4
0 0
0 1
1 0
1 1

3
WDA

4
-1 -1
-1 0
0 -1
0 0

数据规模与约定

对于10%的数据，N=2。

另有20%的数据，保证人物经过的坐标任意一维的绝对值不超过1。

另有10%的数据，保证移动序列只包含D。

另有10%的数据，保证移动序列只包含AD。

另有10%的数据，保证移动序列只包含SD。

另有20%的数据，N=10。

对于100%的数据，$1\le N\le20$。