题目描述

电车的座位按网格排列，网格有 $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. 选择一个空座位，使得该座位与最近的已占用座位的距离最大。
2. 如果有多个这样的座位，选择行号最小的。
3. 如果仍有多个，选择列号最小的。
4. 如果电车为空，乘客会选择座位 $(1, 1)$。

乘客选择座位后会一直坐在那里，直到离开。

给定 $M$ 个事件（按顺序发生），事件有两种类型：

• E：乘客进入电车。
• L P：乘客离开电车，其中 $P$ 是该乘客进入时的事件编号（保证事件 $P$ 是 E 类型，且不会重复离开）。

保证每次乘客进入时，电车至少有一个空座位。

---

输入格式

第一行包含两个整数 $N$ 和 $M$，表示行数和事件数。

接下来 $M$ 行，每行描述一个事件：

• 如果是 E 类型，则只有一个字符 E。
• 如果是 L 类型，则为 L P，其中 $1 \leq P < K$（$K$ 是当前事件编号）。

---

输出格式

对于每个 E 类型的事件，按事件顺序输出一行，包含乘客选择的座位的行号和列号，用空格隔开。

---

样例

样例 1

输入

3 7
E
E
E
L 2
E
L 1
E

输出

1 1
3 2
1 2
3 1
1 1

样例 2

输入

13 9
E
E
E
E
E
E
E
E
E

输出

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

输出

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

---

数据范围与提示

数据比例	$N$ 范围	$M$ 范围
25%	$N \leq 150$	$M \leq 150$
45%	$N \leq 1500$	$M \leq 1500$
65%	$N \leq 1.5 \times 10^5$
100%		$M \leq 3 \times 10^4$

注意：$N$ 可能很大，但 $M$ 相对较小，需要高效算法。

---