ycz的妹子

题目背景

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$输出一个整数

输入输出样例

输入样例 #1

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

输出样例 #1

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$