Online To-Do List Updates

You are given an initially empty to-do list. You must process \(q\) online update operations. There are two types of operations:

1. A s t: Add a task which is published at second \(s\) and requires \(t\) seconds to complete.
2. D x: Delete the \(x\)-th added task.

After each update, compute the earliest time when you can finish all the tasks in the list. Note that only one task can be processed at a time and once started, a task must be finished without interruption.

The optimal schedule is achieved by sorting the tasks by their publication time \(s\) and simulating the processing as follows:

\[ time = 0, \quad \text{for each task }(s,t):\quad time = \max(time, s) + t \]

If the list is empty, the answer is 0.

inputFormat

The first line contains an integer \(q\) representing the number of operations. Each of the following \(q\) lines contains an operation in one of the following two formats:

• A s t: Add a task published at time \(s\) with duration \(t\).
• D x: Delete the \(x\)-th added task.

Operations must be processed online and after each operation, you are to output the earliest finish time of all tasks in the list.

outputFormat

For each operation, output one line containing a single integer, which is the earliest time when all the tasks in the current list can be completed.

sample

5
A 1 2
A 3 2
A 2 1
D 2
A 5 3

3
5
6
4
8

</p>