题目背景

ycz 有很多很多的妹子（ycz：瞎说）

题目描述

机房神犇 ycz 有 $n$ 个青梅竹马，她们分别住在 $1~n$ 号城市中。小时候的她们美丽可爱，但是由于女大十八变，有些妹子的颜值发生了变化，但是十分重感情的 ycz 神犇不忍心抛弃她们，于是记录下来了她们颜值变化的值，我们用 $C, x, y$ 表示第 $x$ 个城市的妹子的颜值下降了 $y$ 。长大之后的 ycz 非常有魅力，有许多妹子被 ycz 迷得神魂颠倒，我们用$I, x, y$ 表示第 $x$ 个城市有一个妹子喜欢上了 ycz ，她的颜值为 $y$ （ $y$ 有可能是负数，但是 ycz 来者不拒）。但在中途有一些妹子和 ycz 吵架了，于是就分手了，我们用 $D, x$ 表示第 $x$ 个妹子和 ycz 分手了。

最近神犇 ycz 要去全国各地找他的妹子们，为了方便计算，我们珂以把 ycz 的妹子所在的城市当作是一条直线，并且挨在一起。神犇 ycz 由于忙于和他的妹子们联系此时已经很累了，于是交给你一个这样的任务：他想知道他在某个时间去找他的所有妹子们珂以获得多大的愉悦度，这个愉悦度为他找的妹子的颜值数，你要做的就是求出这个愉悦度之和（注意长大后妹子们的颜值可能为负数/滑稽）。

注意：每个城市只允许有一个妹子，也就是说后来喜欢上 ycz 的妹子会赶走之前这个城市喜欢 ycz 的妹子~~（一城不容二女）~~。

UPD:

青梅竹马都是喜欢 ycz 的。

分手的第 $x$ 个妹子不是第 $x$ 城市的妹子，是指从前往后数第 $x$ 个有妹子的城市的妹子。

青梅竹马长大后就是妹子。

修改的值 $y$ 不为负数，但是颜值减去之后可能为负数。

输入格式

ycz 有 $5 \times 10^5$ 座城市，开始时，前 $n$ 座城市各有一个妹子，第 $i$ 座城市妹子初始的颜值为 $a_i$。

有 $m$ 次以下四种操作。

• C x y 第 $x$ 座城市的妹子颜值减少 $y$
• I x y 第 $x$ 座城市出现了一个颜值为 $y$ 的妹子，如果在此之前，第 $x$ 座城市已经有妹子，则之前的妹子被驱赶。
• D x 第 $x$ 个有妹子的城市 中的妹子与 ycz 分手
• Q ycz 想知道他所有妹子的颜值总和是多少

输出格式

对于每一个$Q$输出一个整数

5 10
1 2 3 4 5
Q
C 3 2
Q
I 6 6
Q
D 4
Q
C 5 2
I 7 9
Q

15
13
19
15
22

提示

样例解释：

妹子颜值变化如下，删除的就没写在下面了。

1 2 1 4 5
1 2 1 4 5 6
1 2 1 5 6
1 2 1 3 6
1 2 1 3 6 9

对于 30% 的数据，$1 \le n,m \le 10$

对于 70% 的数据，$1 \le n,m \le 1000$

对于 100% 的数据，$1 \le n,m \le 100000,|a_i|,|y| \le 10^9$