#P18740. [正睿NOI2021训练] 第二题

[正睿NOI2021训练] 第二题

第二题

给定长度为 nn 的序列和 mm 个操作,操作编号为 11 至 mm,支持:

  • 1 x y:交换序列第 x,yx,y 个元素。
  • 2 l r v:将序列区间 [l,r][l,r] 的所有元素赋值为 vv。
  • 3 x:查询序列第 xx 个元素。

有 qq 次相互独立的询问。每次给出操作编号区间 [l,r][l,r]:先把整个序列全部置为 00,然后依次执行第 l,l+1,…,rl,l+1,\ldots,r 个操作,求这些操作中所有 3 操作查询结果之和。

输入格式

第一行三个正整数 n,m,qn,m,q。

接下来 mm 行,每行按上述格式描述一个操作。

接下来 qq 行,每行两个整数 l,rl,r,表示一次询问。

输出格式

每次询问输出一行一个整数,表示查询结果之和。

数据范围

1≤n,m,q≤1061\le n,m,q\le10^6。所有序列位置均在 [1,n][1,n] 内,赋值操作的区间满足 1≤l≤r≤n1\le l\le r\le n,赋值 1≤v≤1091\le v\le10^9。询问操作编号满足 1≤l≤r≤m1\le l\le r\le m。答案需要 64 位整数。

样例 1

输入

3 5 3
2 1 3 5
3 2
1 1 3
2 1 1 7
3 1
1 5
2 5
3 5

输出

12

7

7