题目背景

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”。这并不是你随口报的那个假名。

人们又随主持人一并看向天际，一个看着大概五六岁的孩子正跌跌撞撞地跑来。“我是第一名！”他高兴地笑着。他的母亲——太阳神就站在远方，一脸怜爱地看着那个小小的背影。

一轮红日从地平线上喷薄而出。