A6748. 「CEOI2013」电车

**题目译自 [CEOI2013](https://ceoi2013.hsin.hr/) Day1 T2「[Tram](http://ceoi.inf.elte.hu/probarch/13/tasks_day1.pdf)」**

电车上的座位按网格排列，网格由 $N$ 行（编号为 $1$ 到 $N$）和两列（编号为 $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$，表示电车中的行数和事件数。接下来的 $M$ 行包含事件的描述，其中第 $K$ 行包含事件 $K$ 的描述：要么是字符 E，要么是字符 L 后跟一个空格和整数 $P_K$ $(1 \leq P_K < K)$。每个 $P_K$ 都是合法的，即事件 $P_K$ 是 E 类型，并且不会有乘客试图离开两次。

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

输出的行数应该等于输入中 E 类型事件的数量。对于每个 E 类型的事件，按其发生的顺序，在一行中输出乘客选择的座位的行号和列号，用一个空格分隔。

- 对于 $25\%$ 的测试数据，$N \leq 150, M \leq 150$。
- 对于 $45\%$ 的测试数据，$N \leq 1500,M \leq 1500$。
- 对于 $65\%$ 的测试数据，$N \leq 1.5\cdot 10^5, M \leq 1500$。
- 对于 $100\%$ 的测试数据，$1 \leq N \leq 1.5\cdot 10^5, 1 \leq M \leq 3\cdot 10^4$。