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 \leq 3*10^5~