题目背景

翻译自 CEOI 2013 Day 1。

在萨格勒布运营的电车的座位就像一个 $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$（行和列），中间用一个空格隔开。

3 7
E
E
E
L 2
E
L 1
E

1 1
3 2
1 2
3 1
1 1

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

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

提示

对于 $25\%$ 的数据，$n,m\le150$。

对于 $45\%$ 的数据，$n\le1500$。

对于 $65\%$ 的数据，$m\le1500$。

对于 $100\%$ 的数据，$n\le150000,m\le30000$。

前三个测试点是样例。