To-Do List

문제

Wow, your to-do list is empty...but not for long! Over the next few seconds, you’ll have to handle $QQ$ updates to your to-do list.

For the first type of update, you will have to add a new homework assignment to your to-do list. This assignment will be released at the beginning of second $ss$, and will take $tt$ seconds to complete (1 ≤ s, t ≤ 10^6). For the second type of update, you will have to remove the $ii$-th homework assignment that was added to your to-do list.

After each update, you wonder: what’s the earliest time you can finish all of the homework assignments in your to-do list? You can only work on one assignment at a time, and you must finish a homework assignment once you start it without switching to another assignment.

입력

The first line of input contains an integer $QQ$ (1 ≤ Q ≤ 10^6).

The next $QQ$ lines each contain a line starting with a character A or D. A line starting with A represents the first type of update and ends with two space-separated encrypted^∗ integers $s^{\mathrm{\prime }}s\text{'}$ and $t^{\mathrm{\prime }}t\text{'}$. A line starting with D represents the second type of update and ends with an encrypted integer $i^{\mathrm{\prime }}i\text{'}$. It is guaranteed that there have been at least $ii$ assignments added and that the $ii$-th assignment to be added has not been removed yet.

It is guaranteed that there is at least one homework assignment on your to-do list after every update.

---

^∗Note that the input for this problem is encrypted. To decrypt and obtain the actual values of $ss$, $tt$, and $ii$, you may use the following formulas:

• $s=(s^{\mathrm{\prime }}+ans)({10}^6+3)s\; =\; (s\text{'}\; +\; ans)\; \backslash bmod\; (10^6\; +\; 3)$
• $t=(t^{\mathrm{\prime }}+ans)({10}^6+3)t\; =\; (t\text{'}\; +\; ans)\; \backslash bmod\; (10^6\; +\; 3)$
• $i=(i^{\mathrm{\prime }}+ans)({10}^6+3)i\; =\; (i\text{'}\; +\; ans)\; \backslash bmod\; (10^6\; +\; 3)$

Here, $ansans$ represents the answer after the previous update and is initially $00$ before any updates. It may also be useful to note that mod corresponds to the % operator in most programming languages, indicating the remainder after division. For example, $53=25\; \backslash bmod\; 3\; =\; 2$ and $174=117\; \backslash bmod\; 4\; =\; 1$.

출력

Output $QQ$ lines, where the $ii$-th line contains the earliest time (in seconds) you can finish all of the homework assignments in your to-do list after the $ii$-th update.

6
A 3 3
A 2 0
A 999996 999995
D 999991
A 1000000 999994
D 999992

5
11
13
11
13
9

2
A 1000000 1000000
A 4 4

1999999
2999999