Problem Description

You are given a sequence of length $n$ and $m$ operations, numbered from $1$ to $m$. Each operation is one of the following:

1 x y: Swap the two elements at positions $x$ and $y$ in the sequence.

2 l r x: Set all elements in the interval $[l,r]$ of the sequence to $x$.

3 x: Query the value at position $x$ in the sequence.

Now there are $q$ queries. Each query gives an operation interval $[l,r]$:

First set all elements in the sequence to $0$, then perform all operations from $l$ to $r$ in order. Find the sum of the answers of all type $3$ operations among these operations.

Queries are independent.

Input Format

The first line contains three integers $n,m,q$.

Then follow $m$ lines. Each line contains $2$ to $4$ integers, describing an operation.

Then follow $q$ lines. Each line contains two integers $l,r$, meaning that the operations in $[l,r]$ are executed in order, and you need the sum of the answers of all type $3$ operations.

Output Format

For each query, output one integer per line representing the answer.

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

5
5
8
5
8
0

Hint

Idea: nzhtl1477 & ccz181078, Solution: nzhtl1477 & ccz181078, Code: ccz181078, Data: ccz181078.

Constraints:

For $10\%$ of the testdata, $1\le n,m,q\le 1000$.

For $40\%$ of the testdata, $1\le n,m,q\le 10^5$.

For another $20\%$ of the testdata, there is no type $1$ operation.

For another $20\%$ of the testdata, there is no type $2$ operation.

For $100\%$ of the testdata, $1\le n,m,q\le 10^6$, $1\le x\le 10^9$.

Translated by ChatGPT 5