题目描述

某医院有 $m$ 名医生，初始时所有医生均空闲。系统依次接收 $q$ 条按时间非递减顺序给出的指令。每位病人都有唯一编号、优先级和治疗时长；优先级越大越优先，优先级相同则到达时间更早的病人优先，到达时间也相同则编号更小的病人优先。

在处理一条时间为 $t$ 的指令前，系统会先处理所有结束时间不晚于 $t$ 的治疗。医生在时刻 $x$ 治疗结束后，会立刻从当时正在等待的病人中选择优先级最高者开始下一次治疗；若没有等待病人，则该医生保持空闲。随后按输入顺序执行当前指令。每次有空闲医生且存在等待病人时，空闲医生会立即接诊，直到医生或等待病人耗尽。

指令有三种：

• A t id p d：时刻 $t$，编号为 $id$ 的病人到达，优先级为 $p$，治疗时长为 $d$。若被接诊，治疗从当前时刻开始。
• C t id：时刻 $t$，病人 $id$ 请求取消。只有仍在等待的病人才会被取消；已经开始治疗或已经结束的病人不受影响。
• Q t：询问处理完时刻 $t$ 的所有既定步骤后，当前等待人数、正在治疗人数，以及当前等待队首病人的编号。若无人等待，队首编号输出 0。

请依次回答所有询问。

输入格式

第一行两个整数 $m,q$（$1 \le m \le 200000$，$1 \le q \le 200000$），分别表示医生数和指令数。

接下来 $q$ 行，每行一条指令。所有时间 $t$ 满足 $0 \le t \le 10^9$，且按输入顺序非递减。到达指令中的 $id$ 互不相同，$1 \le id \le q$，$1 \le p,d \le 10^9$。取消和询问指令只会引用已经到达过的编号。

输出格式

对每条 Q 指令输出一行三个整数：等待人数、正在治疗人数和当前等待队首编号。

样例

样例 1

输入：

1 8
A 0 1 5 4
A 1 2 9 3
Q 1
C 2 2
Q 2
A 4 3 7 2
Q 4
Q 6

输出：

1 1 2
0 1 0
0 1 0
0 0 0