你是一名深夜加油站的员工。只有当所有车辆都加满油并离开加油站后，你才能下班回家。你工作的加油站有 $P$ 列加油泵，从左到右编号，每列有两个加油泵，分别为泵 A 和泵 B。一个加油泵可以为位于其右侧且油箱盖在左侧的车辆加油，也可以为位于其左侧且油箱盖在右侧的车辆加油。一个加油泵可以同时为左侧和右侧的车辆加油。因此，每个加油泵列都有两条车道供车辆使用。

到达加油站的车辆遵循严格的规则。车辆会前往最左侧且适合其油箱盖位置的空闲车道。如果没有空闲车道，车辆将排队进入适合其油箱盖位置且队列最短的车道。如果存在多个队列长度相同的车道，车辆将排队进入最左侧的那一个。一旦车辆加入队列，就不能切换到其他队列。当车辆加完油离开且车道变为空闲时，该车道队列中的下一辆车将前往使用加油泵。

如果泵 A 可用，则车道为空闲。如果泵 B 可用但泵 A 被占用，则车道不为空闲。当车辆进入空闲车道时，如果两个泵都可用，车辆将前往泵 B，否则将前往泵 A。如果一辆车到达的时间与某些车辆刚好加完油离开的时间相同，那么这辆新车会等待所有其他车辆在队列中移动到空闲的加油泵（如果有的话），然后再决定去哪里排队。当车辆从泵 A 离开，但其前方的泵 B 被占用时，该车辆仍然可以立即离开。

已知第 $i$ 辆车在时间 $t_i$ 到达，需要不到 $f_i$ 分钟加满油并离开，且其油箱盖位于 $s_i$ 侧。

了解以上所有信息后，你想知道你什么时候可以回家。

输入格式

第一行包含两个空格分隔的整数 $1 \le P \le 10$（加油泵列数）和 $1 \le N \le 1000$（到达的车辆总数）。

接下来的 $N$ 行，每行包含两个整数 $1 \le t_i \le 10^5$，$1 \le f_i \le 100$，以及一个表示 $s_i$ 的字符 R 或 L，均由空格分隔。

保证对于所有 $1 \le i < N$，都有 $t_i < t_{i+1}$。

输出格式

输出 $N$ 行，包含每辆车离开加油站的时间，顺序与输入中车辆的顺序一致。

样例

样例输入 1

1 4
1 9 L
2 5 L
3 10 L
4 10 L

样例输出 1

10
7
17
27

样例输入 2

1 4
1 9 L
2 9 L
3 10 L
4 10 L

样例输出 2

10
11
21
21

样例输入 3

1 2
8 11 R
9 10 L

样例输出 3

19
19

样例输入 4

2 10
1 10 R
2 3 R
3 10 R
4 12 R
5 1 R
6 5 R
7 10 R
10 2 R
11 7 R
13 4 R

样例输出 4

11
5
13
16
6
11
21
18
18
22