[JRKSJ R4] risrqnis

 **本题时间限制较长，请勿滥用评测资源。**

给你一个长度为 $n$ 的序列 $a$，有 $q$ 次操作，初始有 $m$ 个空集 $S$，共有两种操作，如下： - `1 l r k`，将 $l\sim r$ 加入集合 $S_k$，即 $S_k\gets S_k\cup\{x|l\le x\le r\}$； - `2 l r k`，查询对于所有 $l\le i\le r$ 的 $a_i$ 中有多少个在集合 $S_k$ 中，即查询 $\displaystyle\sum_{i=l}^r[a_i\in S_k]$。

输入均为非负整数。 第一行 $3$ 个数 $n,q,m$。\ 第二行 $n$ 个数，其中第 $i$ 个数表示 $a_i$。\ 接下来 $q$ 行，每行 $4$ 个数表示一次操作。

输出均为非负整数。 对于每个 `2` 操作，输出一行表示答案。

5 10 2
5 4 3 2 1
2 1 5 1
2 1 5 2
1 2 3 1
1 2 3 2
2 1 4 1
2 1 4 2
1 1 4 1
1 1 4 2
2 1 5 1
2 3 5 2

0
0
2
2
4
3

### 数据规模 | $\text{Subtask}$ | $n,q\le$ | $m\le$ | 分值 | $\text{Time Limit}$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10^6$ | $1$ | $30$ | $1500\text{ ms}$ | | $2$ | $5\times 10^3$ | $3\times 10^5$ | $15$ | $1000\text{ ms}$ | | $3$ | $10^5$ | $10^5$ | $15$ | $1500\text{ ms}$ | | $4$ | $3\times 10^5$ | $10^9$ | $40$ | $3000\text{ ms}$ | 对于 $100\%$ 的数据，$1\le n,q\le 10^6$，$1\le m\le 10^9$，$1\le a_i\le 10^9$。 操作 $1$ 中 $1\le l\le r\le 10^9$，操作 $2$ 中 $1\le l\le r\le n$。所有操作中 $1\le k\le m$。 **没有一个 $\text{Subtask}$ 取到所有数据范围的最大值，各个 $\text{Subtask}$ 都有自己的限制。请阅读数据范围表。** **本题输入文件较大，请使用恰当的读入方式。** **** 深夜，上条当麻的手机响起了收信声。随即，他来到了邮件所写的地方。第七学区的铁桥。 上条到达的时候，发信人早已经等在那了。 「御坂吗……？」 「你忘记的东西。」 她说着丢了什么过来。上条单手接住，发现那是个青娃的手机挂件。他沉入北水洋的时候这东西就应该不见了啊。它用来系到手机上的挂绳当初都粉碎了，现在却换成了其他颜色的绳子。 「好不容易找回来的，别再弄丢了哦。」 「不好意思。」 上条道了声谢，将它再次系到了手机上。 见状，美琴微微一笑。 那是似乎终于把什么东西回归原状而松了一口气的表情。 「我想你这个家伙应该不会一直呆在一个地方的吧…接下来该不会你又要去哪？」 「算是吧。」 上条叹了口气。 「老实说虽然我一副淡定的表情，但实际上我也对究竟发生了什么一头雾水，只知道元凶的名字而已。不过这场骚动已经波及到了学园都市，而正在追查学园都市的我也被卷入其中，被我追查的学园都市同样被卷入……所以我也没办法置之不理了。」 美琴找他似乎就只是为了送挂饰而已。上条将手机放进了口袋。 既然没有了话题，那也只能分别了。 「再见了。」上条说道。 转身背对着美琴，准备离开铁桥， 准备离开这个由科学常识构筑的学园都市，大步迈向外面的领域，而少年的手，却被美琴抓住了。 确确实实地，紧紧拉住想要飘然离开的少年。 在静止的上条耳边，传来了美琴的声音。 「但，这次你不会是一个人了。」