萨格勒布（Zagreb）一辆新有轨电车上的座位排成了一个网格，由 $N$ 行（编号为 $1$ 到 $N$）和 $2$ 列（编号为 $1$ 和 $2$）组成。两个座位（一个在第 $R_A$ 行第 $C_A$ 列，另一个在第 $R_B$ 行第 $C_B$ 列）之间的距离为它们对应网格正方形中心之间的欧几里得距离——即 $\sqrt{(R_A - R_B)^2 + (C_A - C_B)^2}$。

大多数乘客在使用公共交通时更喜欢独处，他们总是试图选择一个尽可能远离其他乘客的座位。更具体地说，当一名乘客进入电车时，他或她会选择一个与最近的已占座位距离最大化的空座位。如果存在多个这样的座位，他们总是会选择行号较小的座位；如果仍然存在多个这样的座位，他们会选择列号较小的座位。乘客选择座位后，会一直坐在那里直到离开电车。如果电车是空的，下一个进入的乘客总是会选择第 $1$ 行第 $1$ 列的座位。

编写一个程序，在给定一系列事件（每个事件为乘客进入或离开电车）的情况下，确定每位乘客坐在哪里。电车最初是空的。

输入中共有 $M$ 个事件，按发生顺序编号为 $1$ 到 $M$。有两种事件：类型为 'E' 的事件对应一名乘客进入电车，而类型为 'L' 的事件对应一名乘客离开电车。对于类型为 'L' 的事件，还会给出一个整数 $P$——它指定在本次事件中离开的乘客是在事件 $P$ 中进入的那个人。

测试数据保证每当有乘客试图进入时，电车中至少有一个空座位。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 150\,000$，$1 \le M \le 30\,000$），分别表示电车的行数和事件的数量。

接下来的 $M$ 行包含事件的描述，其中第 $K$ 行包含第 $K$ 个事件的描述——要么是字符 'E'，要么是字符 'L' 后跟一个空格和整数 $P_K$（$1 \le P_K < K$）。每个 $P_K$ 都是合法的——即事件 $P_K$ 的类型为 'E'，且没有乘客会尝试离开两次。

输出格式

输出的行数应等于输入中 'E' 类型事件的数量。

对于每个 'E' 类型的事件，按照它们发生的顺序，在单行中输出该乘客选择的座位的行号和列号，用单个空格分隔。

子任务

• 在占总分 25 分的测试用例中，满足 $N \le 150$ 且 $M \le 150$。
• 在占总分 45 分的测试用例中，满足 $N \le 1500$ 且 $M \le 1500$。
• 在占总分 65 分的测试用例中，满足 $N \le 150\,000$ 且 $M \le 1500$。

样例

输入样例 1

3 7
E
E
E
L 2
E
L 1
E

输出样例 1

1 1
3 2
1 2
3 1
1 1

输入样例 2

13 9
E
E
E
E
E
E
E
E
E

输出样例 2

1 1
13 2
7 1
4 2
10 1
2 2
3 1
5 1
6 2

输入样例 3

10 9
E
E
E
E
L 3
E
E
L 6
E

输出样例 3

1 1
10 2
5 2
7 1
4 2
2 2
4 1