暂无测试数据。

题目描述

幽香是幻想乡中一个非常有地位的人。她日理万机，事务繁多，感到自己已经快管理不过来了。于是她决定开发一个日程管理软件来帮助自己管理任务。

对于每个任务 \(i\) 有一个对应的截止日期 \(t_i\) 以及收益 \(p_i\)，表示若幽香能在不晚于第 \(t_i\) 天完成这个任务，便可以得到的 \(p_i\) 收益。幽香办事的能力非常强，任何任务都可以用恰好一天时间做完。但由于任务实在太多了，有时候并不能完成所有任务，于是幽香会想要知道这个情况下，完成任务可以给她带来最大的累积收益是多少。

由于幻想乡的人们十分善变，任务总是不断发生着变化。幽香希望这个管理软件还能够支持插入一个任务，和删除一个任务的操作。

具体的说，幽香希望支持以下2个操作：

1. ADD t p：表示新添一个截止日期为\(t\)，收益为 \(p\) 的任务。

2. DEL t p：表示删除一个截止日期为 \(t\)，收益为 \(p\) 的任务。如果有多个这样的任务，只删除一个。数据保证这样的任务一定存在。

在每次操作执行完毕后，你都需要输出能够完成的任务的最大收益和。

幽香一共有 \(T\) 天需要安排，从第 1 天到第 \(T\) 天。你能帮助她写出这个高效率的软件吗？

输入

第一行，有两个正整数 \(T\) 和 \(Q\)，表示天数和操作的个数。

接下来 \(Q\) 行，其中第 \(i\) 行表示第 \(i\) 个操作，形式为 ADD t p 或 DEL t p，其具体意义如题面所述。

输出

要求对于每一次操作，输出一个整数在执行完该操作后幽香能获得的最大收益和。

样例 1

输入

5 10
ADD 1 5811
ADD 3 5032
DEL 3 5032
ADD 3 5550
ADD 5 3486
DEL 1 5811
DEL 3 5550
ADD 4 5116
ADD 3 9563
ADD 5 94

输出

5811
10843
5811
11361
14847
9036
3486
8602
18165
18259

数据范围限制

数据保证，\(1\le T,Q\le 3\times 10^5\)。

限制

每个测试点时限：3秒
内存限制：2333MB

来源

CTSC2015