题目背景

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

题目描述

给你一个长度为 $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$			$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}$ 都有自己的限制。请阅读数据范围表。

本题输入文件较大，请使用恰当的读入方式。

---

深夜，上条当麻的手机响起了收信声。随即，他来到了邮件所写的地方。第七学区的铁桥。

上条到达的时候，发信人早已经等在那了。

「御坂吗……？」

「你忘记的东西。」

她说着丢了什么过来。上条单手接住，发现那是个青娃的手机挂件。他沉入北水洋的时候这东西就应该不见了啊。它用来系到手机上的挂绳当初都粉碎了，现在却换成了其他颜色的绳子。

「好不容易找回来的，别再弄丢了哦。」

「不好意思。」

上条道了声谢，将它再次系到了手机上。

见状，美琴微微一笑。

那是似乎终于把什么东西回归原状而松了一口气的表情。

「我想你这个家伙应该不会一直呆在一个地方的吧…接下来该不会你又要去哪？」

「算是吧。」

上条叹了口气。

「老实说虽然我一副淡定的表情，但实际上我也对究竟发生了什么一头雾水，只知道元凶的名字而已。不过这场骚动已经波及到了学园都市，而正在追查学园都市的我也被卷入其中，被我追查的学园都市同样被卷入……所以我也没办法置之不理了。」

美琴找他似乎就只是为了送挂饰而已。上条将手机放进了口袋。

既然没有了话题，那也只能分别了。

「再见了。」上条说道。

转身背对着美琴，准备离开铁桥，

准备离开这个由科学常识构筑的学园都市，大步迈向外面的领域，而少年的手，却被美琴抓住了。

确确实实地，紧紧拉住想要飘然离开的少年。

在静止的上条耳边，传来了美琴的声音。

「但，这次你不会是一个人了。」