小旭追女神-三国乱世

Time Limit: 1200 ms Memory Limit: 65536 KiB

Problem Description

最近室友都开始玩起来三国杀了,这让小旭很郁闷,(因为小旭不会啊),所以为了能和小伙伴们一起玩耍,小旭决定重读三国,一天小旭晚上梦回三国。
话说: 太祖武皇帝,沛国谯人也,姓曹,讳操,字孟德,汉相国参之后。桓帝世,曹腾为中常侍大长秋,封费亭侯。养子嵩嗣,官至太尉,莫能审其生出本末。嵩生太祖。:太祖一名吉利,小字阿瞒。王沈魏书曰:其先出于黄帝。当高阳世,陆终之子曰安,是为曹姓。周武王克殷,存先世之后,封曹侠于 邾。春秋之世,与于盟会,逮至战国,为楚所灭。子孙分流,或家于沛。汉高祖之起,曹参以功封平阳侯,世袭爵土,绝而复绍,至今适嗣国于容城。司马彪续汉书曰:腾父节,字符伟,素以仁厚称。邻人有亡豕者,与节豕相类,诣门认之,节不与争;后所亡 豕自还其家,豕主人大惭,送所认豕,并辞谢节,节笑而受之。由是乡党贵叹焉。长子伯兴,次子仲兴,次子叔兴。腾字季兴,少除黄门从官。永宁元年,邓太后诏 黄门令选中黄门从官年少温谨者配皇太子书,腾应其选。太子特亲爱腾,饮食赏赐与觽有异。顺帝即位,为小黄门,迁至中常侍大长秋。在省闼三十余年,历事四 帝,未尝有过。
额。。。。。小旭进错梦了,重来:
滚滚长江东逝水,浪花淘尽英雄。是非成败转头空。
青山依旧在,几度夕阳红。白发渔樵江渚上,惯
看秋月春风。一壶浊酒喜相逢。古今多少事,都付
笑谈中。
                ——调寄《临江仙》
话说天下大势,分久必合,合久必分。周末七国分争,并入于秦。及秦灭之后,楚、汉分争,又并入于汉。汉朝自高祖斩白蛇而起义,一统天下,后来光武中兴,传至 献帝,遂分为三国。推其致乱之由,殆始于桓、灵二帝。桓帝禁锢善类,崇信宦官。及桓帝崩,灵帝即位,大将军窦武、太傅陈蕃共相辅佐。时有宦官曹节等弄权, 窦武、陈蕃谋诛之,机事不密,反为所害,中涓自此愈横。
且说小旭在梦境中成为曹操手下的狗头军师(为什么是军师呢?我也不知道),小旭很是得意啊
说道:
挂印封金辞汉相,寻兄遥望远途还。 马骑赤兔行千里,刀偃青龙出五关。
忠义慨然冲宇宙,英雄从此震江山。 独行斩将应无敌,今古留题翰墨间。
至于小旭为什么会说这首诗我也不知知道 ,可能精神错乱了吧。
一天,曹操找小旭
曹操:小旭军师,本王找你帮我做点事。
小旭:大王请直言。
曹操:好,现在刘备大势已成,我要加强防备,现在请军师将16号军营增加5人。
小旭:遵命。
曹操:将8号军营增加1人。
小旭:遵命。
曹操:从第8营到第12营共有多少人?
小旭:。。。。。。
曹操:这都不知道,来人拉出去斩了。
小旭吓的 赶紧给数据结构教授打电话(不要问我三国为什么会有电话,任性)。
教授:让你平时不好好刷题,自己解决。
你能帮小旭解决之个问题吗?

Input

多组输入,每组数据第一行是两个整数n,m(1 < = n,m < = 1000000),接下来一行是n个数,代表相对应的军营的人数。接下来m行,每行可能的操作:1 UPDATE x d,表示第x个军营人数增加d(0 = < d < = 100), 2 QUERY L R 表示询问从第 L个军营到第R个军营之间的总人数。

Output

 对于每组数据中的询问,输出询问值。每组数据后面有一个空行。

Sample Input

4 7
78 16 94 36 
QUERY 1 2 
UPDATE 4 62 
QUERY 4 4 
QUERY 1 3 
QUERY 1 4 
QUERY 4 4 
UPDATE 2 35

Sample Output

94 
98 
188 
286 
98 

Hint

Source