Description

给定一系列事件，每个事件都是乘客进入或离开电车。你需要输出这位乘客进入时他会坐在哪里。电车一开始是空的。

输入中有 $m$ 个事件，按事件发生的顺序编号为 $1$ 到 $m$。有两种事件：E 类事件表示乘客进入有轨电车，而 L 类事件则表示乘客离开有轨电车。对于类型为 L 的事件，还给出了一个整数 $p$，它表示在该事件中离开的乘客是在事件 $p$ 中进入的乘客。

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

Input Format

第一行输入包含两个整数 $n$ 和 $m$。

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

Output Format

输出中的行数应等于输入中 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

Hint

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

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

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

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

前三个测试点是样例。