题目背景

译自 CCC 2025 Senior T5。本题满分为 $15$。

题目描述

你的待办事项列表现在是空的。但是你需要处理 $q$ 次对待办事项列表的更新：

• $\texttt{A}$ $s$ $t$：

  向你的待办事项列表内加入一个任务：这个任务在第 $s$ 秒发布，需要 $t$ 秒完成。

• $\texttt{D}$ $x$：

  删除第 $x$ 个被加入的任务。

在每次操作后，求出最早能在什么时候完成列表中所有的任务。

一次只能完成一个任务。一旦开始一个任务，必须一口气完成，不能中途去做别的任务。

为了锻炼你的水平，我们会使用一些手段让你在线处理更新。

输入格式

第一行，一个正整数 $q$。

接下来 $q$ 行，每行一个大写字母 $c\in \texttt{A},\texttt{D}$ 和若干个非负整数，描述一次加密的操作：

• $\texttt{A}$ $s'$ $t'$
• $\texttt{D}$ $x'$

令 $p=10^6+3$，$\mathrm{last}$ 表示上一次更新后的答案（如果不存在，定义为 $0$）。则 $s=(s'+\mathrm{last})\bmod p$，$t=(t'+\mathrm{last})\bmod p$，$x=(x'+\mathrm{last})\bmod p$。

你的待办事项列表现在是空的。但是你需要处理 $q$ 次对待办事项列表的更新：

• $\texttt{A}$ $s$ $t$：

  向你的待办事项列表内加入一个任务：这个任务在第 $s$ 秒发布，需要 $t$ 秒完成。

• $\texttt{D}$ $x$：

  删除第 $x$ 个被加入的任务。

在每次操作后，求出最早能在什么时候完成列表中所有的任务。

一次只能完成一个任务。一旦开始一个任务，必须一口气完成，不能中途去做别的任务。

为了锻炼你的水平，我们会使用一些手段让你在线处理更新。

数据保证不会删除不存在（或已被删除）的任务，且保证在每次更新后，列表中至少有一个任务。

输出格式

输出 $q$ 行，每行一个正整数，表示答案。

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

提示

样例解释

• 样例 $1$ 解释：

加密前的样例 $1$ 为

6
A 3 3
A 7 5
A 4 3
D 1
A 8 2
D 2

• 在第一次更新后，我们可以在第二秒的开始时开始第一次任务，并在第五秒的结束时完成（区间 $[3, 5]$）。

• 在第二次更新后，我们可以在区间 $[3, 5]$ 上完成第一次任务，在区间 $[7, 11]$ 上完成第二次任务。

• 在第三次更新后，我们可以在区间 $[3, 5]$ 上完成第一次任务，在区间 $[6, 8]$ 上完成第三次任务，然后在区间 $[9, 13]$ 上完成第二次任务。

• 在第四次更新后，我们可以在区间 $[4, 6]$ 上完成第三次任务，在区间 $[7, 11]$ 上完成第二次任务。

• 在第五次更新后，我们可以在区间 $[4, 6]$ 上完成第三次任务，在区间 $[7, 11]$ 上完成第二次任务，然后在区间 $[12, 13]$ 上完成第四次任务。

• 在第六次更新后，我们可以在区间 $[4, 6]$ 上完成第三次任务，在区间 $[8, 9]$ 上完成第四次任务。

• 样例 $2$ 解释：

加密前的样例 $2$ 为

2
A 1000000 1000000
A 1000000 1000000

子任务

对于 $100\%$ 的数据，保证：

• $1\le q\le 10^6$；
• $1\le s,t\le 10^6$；
• 不会删除不存在（或已被删除）的任务。
• 在每次更新后，列表中至少有一个任务。

---

• $\text{Subtask 0(0 points)}$：样例。
• $\text{Subtask 1(2 points)}$：$q\le 3000$。
• $\text{Subtask 2(6 points)}$：只有第一种更新。
• $\text{Subtask 3(7 points)}$：无额外限制。