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

Given a sequence of $m$ operations, indexed from $1$ to $m$. The 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. Each query provides $L, R$, asking for the sum of the answers of all summation operations performed when the sequence $a$ is initialized to $0$ and operations from index $L$ to $R$ (inclusive) are executed 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 one integer, representing the answer to each query in order.

Constraints

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 constraints.

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