Given a sequence of length $n$ and $m$ operations, indexed from $1$ to $m$. Each operation is one of the following:

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

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

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

There are $q$ queries. Each query provides a range of operations $[l, r]$. For each query, the sequence is first reset to all zeros, then operations from $l$ to $r$ are performed sequentially. You need to calculate the sum of the results of all type 3 operations performed within that range.

Queries are independent of each other.

Input

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

The next $m$ lines each contain 2 to 4 integers, representing each operation in order.

The next $q$ lines each contain two integers $l, r$, representing the range of operations to perform for each query.

Output

For each query, output a single integer representing the answer on a new line.

Examples

Input 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

Output 1

5
5
8
5
8
0

Constraints

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

• For $10\%$ of the data, $1 \le n, m, q \le 1000$.
• For $40\%$ of the data, $1 \le n, m, q \le 10^5$.
• For another $20\%$ of the data, there are no type 1 operations.
• For another $20\%$ of the data, there are no type 2 operations.
• For $100\%$ of the data, $1 \le n, m, q \le 10^6$, $1 \le x \le 10^9$.