旭日东升

238 神教 #3 ——还有多久，太阳才会出来？ ——不知道…… 在古老的传说中，你家附近的小村，由于惹怒了太阳神而被罚去了日光。庄稼纷纷枯死了，人们在寒冷与饥饿中求生。而小村的附近，除了你家以外，就是一片大荒。 神学开始在小村中兴起。越来越多的人成为了神学家，在当年集资修建的图书馆中没日没夜地研读着古籍。终于，大家在图书馆仓库的一个阴暗潮湿的角落里发现了一本—— 古老而破旧的，据说早已失传的《祈日术》。

书里的许多记载已不可辨识。根据残存的篇章，大家只能推测是要举办一场比赛，非常困难的比赛。至于比完之后怎么处理，完全没有头绪。 但大家决定试试，哪怕是自己摸索呢？ 于是当你路过村子的时候，便看见展板上挂了这么一道题——唯一的比赛题。 > 维护一个不可重集合的序列 $a$，长度为 $n$。支持以下两种操作： > 1. 给定 $l,r,x$，对于每个 $l\le i\le r$，将 $x$ 并入 $a_i$。 > 2. 给定 $l,r$，设 $S$ 把每个 $l\le i\le r$ 的 $a_i$ 并在一起的集合，输出 $S$ 中所有元素的和。 你看了看自己随身带着的电脑，决定去捧（za）个场。 那么，加油吧！

输入数据的起始会有一个长度为 $2$ 的字符串，见【提示说明】处。它们可以用来帮你快速判断数据性质。 第二行两个正整数 $n,m$ 表示集合序列的长度和操作的次数，初始的集合 $a_1,a_2,\cdots,a_n$ 均为空。 接下来 $m$ 行每行先是三个正整数 $op,l,r$ 如题。如果 $op=1$，那么这一行还会有一个正整数 $x$ 如题。

对于每行 $op=2$ 的输入，分别输出一个正整数，依次表示每次查询的结果。

II
11 13
1 6 8 4
2 7 7
2 2 4
2 11 11
1 1 11 2
1 5 5 5
1 8 11 3
2 1 8
1 5 10 2
1 2 4 4
2 2 10
2 3 9
2 2 4

4
0
0
14
14
14
6

**本题采用捆绑测试。** 对于 $100\%$ 的数据，保证 $1\le n,m,x\le10^5,1\le l\le r\le n$。 Subtask 1：对于 $10\%$ 的数据，保证 $1\le n,m,x\le100$; Subtask 2：对于 $10\%$ 的数据，保证 $1\le n,m,x\le10^5$，第一行的字符串为 `PP`; Subtask 3：对于 $20\%$ 的数据，保证 $1\le n,m,x\le10^5$，第一行的字符串为 `IP`; Subtask 4：对于 $30\%$ 的数据，保证 $1\le n,m,x\le10^5$，第一行的字符串为 `PI`; Subtask 5：对于最后 $30\%$ 的数据，无特殊限制。 --- 输入第一行的字符串作用：该字符串包含两个为 `P` 或 `I` 的字符。如果第一个字符为 `P`，那么所有修改操作均满足 $l=r$；如果第二个字符为 `P`，那么所有查询操作均满足 $l=r$。对应位置为 `I` 表示无限制。 --- 毫无疑问，你获得了第一名。 “好的，那么我们现在来宣读获奖名单！” “第三名：……”（掌声，颁奖） “第二名：……”（掌声，颁奖） “第一……” 主持人突然停下来，揉揉眼睛，随即惶恐地看着天空。附近的人们好奇地凑上去看主持人手中的名单。只见第一名的名字正以一种不可名状的方式剧烈扭曲重构着，反复地在两种不同形态之间变换。 名单的上方突然出现了几个字符。随着字符逐渐变得清晰，人们看清了，是四个意义不明，但看着十分不耐烦的字符：“div1”。 这时，第一名的名字的变动也稳定了下来——就好像其中有一方主动退出了一样。 最终，名字固定在了五个字母：“David”。这并不是你随口报的那个假名。 人们又随主持人一并看向天际，一个看着大概五六岁的孩子正跌跌撞撞地跑来。“我是第一名！”他高兴地笑着。他的母亲——太阳神就站在远方，一脸怜爱地看着那个小小的背影。 一轮红日从地平线上喷薄而出。