中国跳棋是一种策略性棋盘游戏，可以由两名、三名、四名或六名玩家进行，既可以单人对战，也可以组队合作。

六名玩家正在进行一种新规则的中国跳棋，其规则与传统规则不同。

1. 如图所示，棋盘呈星形，每个玩家拥有一个角。图中的圆圈代表一个空格。显然，棋盘共有 17 行，不同行可能包含不同数量的空格。每个玩家的角由 10 个空格组成。
2. 每位玩家有 10 枚棋子。游戏开始时，每位玩家将所有棋子放在自己的角上，每枚棋子占据一个空格。
3. 玩家轮流移动一枚棋子，移动方式为：移动一步到相邻的空格，或者在六个方向（左、右、左上、右上、左下、右下）之一跳过对称图案（包含至少一枚棋子）到达一个空格。 例如，当 E 为空格时，棋子可以从 A 跳到 E，当且仅当： 1) C 处有一枚棋子，而 B 和 D 为空格， 2) 或者 B 和 D 处各有一枚棋子，而 C 为空格， 3) 或者 B、C 和 D 处各有一枚棋子。 当 D 为空格时，棋子可以从 A 跳到 D，当且仅当 B 和 C 处各有一枚棋子。
4. 玩家 1 先行动，然后是玩家 2，以此类推。
5. 玩家永远不能将棋子移入他人的角，除非是与其自身角相对的角。例如，玩家 6 可以将棋子移入自己的角或玩家 5 的角。

当六名玩家轮流行动时，他们会选择一枚棋子和一个方向，然后总是将棋子移动到尽可能远的位置。给定他们在前 $N$ 个回合中选择的棋子和方向，你能告诉我们他们的棋子最终位于何处吗？

输入格式

输入包含多组测试数据。（最多 1000 组） 对于每组测试数据： 第一行包含一个整数 $N$，表示回合数。（$1 \le \sum N \le 10^5$） 接下来 $N$ 行，每行包含两个整数 $x, y$ 和一个方向，以空格分隔。这表示玩家选择了位于第 $x$ 行第 $y$ 个空格处的棋子，并将其沿该方向移动。

为简便起见，方向以缩写形式给出。L 表示左，R 表示右，UL 表示左上，UR 表示右上，LL 表示左下，LR 表示右下。

如果玩家在第 $x$ 行第 $y$ 个空格处没有棋子，或者棋子无法沿给定方向移动，请跳过该回合（该玩家本回合不进行任何操作）。保证给定的位置和方向是有效的。

输出格式

对于每组测试数据，输出六行。第 $i$ 行包含二十个整数 $x_1, y_1, x_2, y_2, \dots, x_{10}, y_{10}$，以空格分隔，表示玩家 $i$ 的棋子位置。第 $j$ 枚棋子位于第 $x_j$ 行第 $y_j$ 个空格。位置应先按 $x$ 升序排序，再按 $y$ 升序排序。

样例

样例输入 1

12
1 1 LL
16 1 UL
10 1 R
5 11 L
11 10 L
7 1 LR
2 2 LR
13 5 UL
12 2 R
5 12 L
11 11 L
6 1 LR

样例输出 1

2 1 3 1 3 2 3 3 4 1 4 2 4 3 4 4 5 5 6 9
12 4 14 1 14 2 14 3 14 4 15 1 15 2 15 3 16 2 17 1
10 2 11 1 11 2 12 1 12 3 12 5 13 1 13 2 13 3 13 4
5 7 5 9 5 10 5 13 6 10 6 11 6 12 7 10 7 11 8 10
10 10 11 7 11 9 12 10 12 11 12 12 13 10 13 11 13 12 13 13
5 1 5 2 5 3 5 4 6 2 6 3 7 1 7 2 8 1 11 3

Figure 1. 棋盘呈星形，每个玩家拥有一个角。