题目描述

在$zty$的梦中，有这样一个奇怪的世界：

世界初始时为一个$n*n$个格子的正方形平面，每个格子都有一个唯一且不会更改的标号。

初始时，左下角格子的标号为$(1, 1)$，右上角格子的标号为$(n, n)$。

初始时，$zty$位于标号为$(1, 1)$的格子。

对于$zty$来说，他可以向上下左右移动。一次移动只会走到相邻的格子。例如，在没有任何消除格子操作的情况下（详见下方题目描述），若$zty$当前所在格子标号为(2, 2)，向右移动后所在格子标号为(3, 2)，向上移动后所在格子标号为(2, 3)。

$zty$在改造这个世界。除了移动之外，他可以实施操作，消除当前所在位置的格子。格子消除后，该格子左面的格子会和右面的格子左右相邻，上面的格子会和下面的格子上下相邻。

例如，在初始的世界中，消除标号为(2, 2)的格子，则

（以下 (x, y) 代表标号为 (x, y) 的格子）

(3, 2)的左边会由(2, 2)变成(1, 2)

(1, 2)的右边会由(2, 2)变成(3, 2)

(2, 1)的上面会由(2, 2)变成(2, 3)

(2, 3)的下面会由(2, 2)变成(2, 1)

若再消除标号为(2, 3)的格子，则

(2, 1) 的上面会由(2, 2)变成(2, 4)

(2, 4) 的下面会由(2, 2)变成(2, 1)

(1, 3) 的右面会由(2, 3)变成(3, 3)

(3, 3) 的左面会由(2, 3)变成(1, 3)

除此之外，还有查询操作，询问zty当前所在的格子的标号。

zty的操作，还会遵循以下规则：

1、若此时位于世界的边缘，且此次移动操作会导致zty越界，则此次移动不会执行。例如，在zty位于初始局面的标号为(1,1)的格子时，若向下 / 左移动，则不会执行。

2、若执行“消除当前格子”的操作，当且仅当zty离开该格子后，其才会被消除。例如，zty位于标号(2,2)的格子时，执行了一次“消除当前格子”的操作，则在zty离开(2, 2)前，标号为(2, 2)格子仍然存

在。对应到题目操作中的解释为：若此时查询所在格子的标号，仍为(2, 2)

3、任意两个“消除当前格子”的操作之间，一定间隔着至少一次移动操作。

输入格式

第一行两个整数$n(1 ≤ n ≤ 500)$，表示世界起始的大小，其含义见题目描述。

第二行一个整数$T(T ≤ 10^6)$，代表操作的次数。

接下来$T$ 行，每行一个字符。

若字符为 $W/ S /A /D$，分别代表此次向上 / 下 / 左 / 右移动。

若字符为$B$，代表实行一次消除操作。

若字符为$P$ ，代表一次查询操作，询问$zty$当前所在格子的标号。

输入数据保证任意两个消除操作之间，一定间隔着至少一次移动操作（符合上述规则三）。

输出格式

设$|P|$为输入数据中字符$P$ 的个数。

输出共$|P|$行，每行一个形如 (x, y) 的坐标，表示当前当前所在的格子的标号.

样例

15
14
W
B
S
A
W
S
D
P
W
A
W
S
P
D

(2, 1)
(2, 2)

每次操作后所在格子的标号：

(1, 2) (1, 2) (1, 1) (1, 1) (1, 3) (1, 1) (2, 1) (2, 1) (2, 2) (2, 2) (2, 3) (2, 2) (2, 2) (3, 2)

数据范围

本题共有10个测试点。

对于$30\%$的数据，$1 ≤ n ≤ 20，1 ≤ T ≤ 20$。

对于$50$的数据，$1 ≤ n ≤ 100，1 ≤ T ≤ 10^4$。

对于$100\%$的数据，$1 ≤ n ≤ 500，1 ≤ T ≤ 10^6$。