题目描述

给一个长为 $n$ 的序列，有 $m$ 个操作，操作编号从 $1$ 到 $m$，每个操作为：

1 x y：将序列位置为 $x,y$ 的两个元素交换。

2 l r x：将序列区间 $[l,r]$ 内所有元素修改为 $x$。

3 x：查询序列 $x$ 位置的值。

现在有 $q$ 次查询，每次查询给出一个操作的区间 $[l,r]$：

先将序列中的元素全部置为 $0$，之后依次进行从 $l$ 到 $r$ 的所有操作，求出所有这些操作中所有 $3$ 操作的答案的和。

查询之间独立。

输入格式

第一行三个数表示 $n,m,q$。

之后 $m$ 行，每行 $2$ 到 $4$ 个数，依次表示每个操作。

之后 $q$ 行，每行两个数 $l,r$，查询依次进行 $[l,r]$ 的所有操作，所有 $3$ 操作的答案的和。

输出格式

对于每次查询，输出一行一个数表示答案。

样例 #1

样例输入 #1

5 10 6
3 1
3 5
2 5 5 10
3 1
2 5 5 5
3 5
3 1
1 1 5
2 5 5 3
3 5
5 6
3 6
1 10
2 8
3 10
7 8

样例输出 #1

5
5
8
5
8
0

提示

Idea：nzhtl1477&ccz181078，Solution：nzhtl1477&ccz181078，Code：ccz181078，Data：ccz181078

对于 $10\%$ 的数据，满足 $1\le n,m,q\le 1000$。

对于 $40\%$ 的数据，满足 $1\le n,m,q\le 10^5$。

对于另外 $20\%$ 的数据，没有 $1$ 操作。

对于另外 $20\%$ 的数据，没有 $2$ 操作。

对于 $100\%$ 的数据，满足 $1\le n,m,q\le 10^6$，$1\le x\le 10^9$。