Given an integer sequence $a_1, \dots, a_n$ of length $n$.

Given a sequence of $m$ operations, indexed from $1$ to $m$. The operation sequence contains modification operations and summation operations. A modification operation is given by $l, r, v$, which sets $a_l, a_{l+1}, \dots, a_r$ to $v$. A summation operation is given by $l, r$, which queries $\sum_{i=l}^r a_i$.

There are $q$ queries in total. Each query provides $L, R$, asking for the sum of the results of all summation operations when the sequence $a$ is initialized to $0$ and operations from index $L$ to $R$ in the operation sequence are performed sequentially.

Input

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

The next $m$ lines each contain either $1, l, r, v$ or $2, l, r$, representing an operation.

The next $q$ lines each contain two integers $L, R$, representing a query.

Output

Output $q$ lines, each containing an integer representing the answer to the corresponding query.

Examples

Input 1

10 5 4
1 9 10 7
1 7 10 9
2 3 10
1 10 10 1
2 5 10
2 5
1 1
3 4
1 3

Output 1

64
0
0
36

Subtasks

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

For all data, $1 \le l \le r \le n$, $1 \le v \le n$, $1 \le L \le R \le m$, $1 \le n, m, q \le 5 \times 10^5$.

For $10\%$ of the data, $n, m, q \le 10^2$.

For another $20\%$ of the data, $n, m, q \le 5 \times 10^3$.

For another $10\%$ of the data, every operation is a summation operation.

For another $20\%$ of the data, every query satisfies $L = 1$.

For another $20\%$ of the data, $n, m, q \le 2 \times 10^5$.

For the remaining data, there are no special restrictions.