Problem Description

There are $T$ days and multiple tasks on a calendar, each task has two attributes, a deadline $t_i$, and a profit $p_i$, meaning the task has to be completed by day $t_i$ to earn a profit of $p_i$. Each task only takes one day to complete, the calendar needs to support the following two operations.

1. ADD t p: Add a task with deadline t and profit p
2. DEL t p: Delete the task with deadline t and profit p, if multiple exists, delete any one of those. The data gurantees at least one exists.

After every operation, output the maximum profit after $T$ days.

Input Specifications

The first line are two integers $T,Q$, denoting the number of days on the calendar, and the number of operations

Output Specifications

$Q$ lines, each line containing the maximum profit after $T$ day after each operation.

Sample Input

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

Sample Output

5811
10843
5811
11361
14847
9036
3486
8602
18165
18259

Data

$T,Q\le 3\ast {10}^5$