P9270 [CEOI 2013] 有轨电车 / Tram

翻译自 [CEOI 2013 Day 1](https://ceoi2013.hsin.hr/tasks/tasks_day1.pdf)。 在萨格勒布运营的电车的座位就像一个 $n$ 行 $2$ 列的网格，两个座位之间的距离，是相应网格正方形中心之间的欧几里得距离（直线距离）。 大多数乘客在使用公共交通工具时会社恐，也就是说，当乘客进入电车时，会选择一个没有人坐的座位，并且该座位与最近的座位的距离尽可能大。如果有多个这样的座位，他们总是会选择一个行号较小的座位（因为这样他不需要走太远）。如果仍然有多个这种座位，他们会选择列号较小（即列号为 $1$）的座位。乘客选择座位后，会一直坐在那里，直到他离开电车。如果电车是空的，进入的乘客将始终选择第 $1$ 排第 $1$ 列的座位。

给定一系列事件，每个事件都是乘客进入或离开电车。你需要输出这位乘客进入时他会坐在哪里。电车一开始是空的。 输入中有 $m$ 个事件，按事件发生的顺序编号为 $1$ 到 $m$。有两种事件：`E` 类事件表示乘客进入有轨电车，而 `L` 类事件则表示乘客离开有轨电车。对于类型为 `L` 的事件，还给出了一个整数 $p$，它表示在该事件中离开的乘客是在**事件** $p$ 中进入的乘客。 测试数据确保每当乘客试图进入电车时，电车中至少有一个空位。

第一行输入包含两个整数 $n$ 和 $m$。 接下来 $m$ 行，其中第 $i$ 行表示事件 $i$ 的内容，首先输入一个字符 `E` 或 `L`，当字符是 `L` 时再输入一个数 $p_i$，保证事件 $p_i$ 的类型一定是 `E`。

输出中的行数应等于输入中 `E` 类事件的数量。对于第 $i$ 个类型为 `E` 的事件，在第 $i$ 行上输出该乘客选择的座位号 $r,c$（行和列），中间用一个空格隔开。

对于 $25\%$ 的数据，$n,m\le150$。 对于 $45\%$ 的数据，$n\le1500$。 对于 $65\%$ 的数据，$m\le1500$。 对于 $100\%$ 的数据，$n\le150000,m\le30000$。 前三个测试点是样例。