科格国王对他的骑士们一贯的松懈感到恼火——他们可以在没有事先通知的情况下闯入他的大厅!因此,国王决定建立一个带有队列的接待处,每个骑士提前选择他来的时间和访问需要多长时间。骑士们按照记录的时间顺序接受服务,但每个骑士必须等到他之前的所有骑士都访问完毕。
Keabeanie 公主想见她的父亲。然而,她不想打扰骑士们,所以她加入了队列。不幸的是,骑士们经常改变主意——他们可以加入队列或取消访问。根据接待处的记录,请帮助公主了解如果她在指定时间排队,她需要等待多长时间才能见到父亲。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 3 \cdot 10^5$$$) — 事件数。事件可以分为三种类型: 加入, 取消,或 查询.
- 加入“+ $$$t$$$ $$$d$$$" ($$$1 \leq t, d \leq 10^6$$$) — 一个新骑士加入队列,其中 $$$t$$$ 是骑士到来的时间,$$$d$$$ 是访问的持续时间。
- 取消“- $$$i$$$" ($$$1 \leq i \leq q$$$) — 骑士取消访问,其中 $$$i$$$ 是所有事件列表中相应加入事件的编号(从 1 开始计数)。
- 查询“? $$$t$$$" ($$$1 \leq t \leq 10^6$$$) — Keabeanie 询问如果她在 $$$t$$$ 时间到达,她会等多久。
保证每次活动结束后队列中不存在两个进入时间相同的骑士。取消事件是指之前尚未取消的连接。
Keabeanie可以和一些骑士同时到来,但是Keabeanie非常有礼貌,她会等待骑士通过。
输出
对于每个查询,单独一行写出 Keabeanie 必须等待的时间。
示例
输入复制
19 ? 3 + 2 2 ? 3 ? 4 + 5 2 ? 5 ? 6 + 1 2 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 9 - 8 ? 2 ? 3 ? 6
输出复制
0 1 0 2 1 3 2 1 2 1 0 0 2 1 1