Problem Description

You are given an integer sequence $a_1, \dots, a_n$ of length $n$.

You are given an operation sequence consisting of $m$ operations, numbered from $1$ to $m$. The sequence contains assignment operations and range sum operations. An assignment operation gives $l, r, v$, and sets $a_l, a_{l+1}, \dots, a_r$ to $v$. A range sum operation gives $l, r$, and queries $\sum \limits_{i=l}^r a_i$.

There are $q$ queries. Each query gives $L, R$, asking for the sum of answers of all range sum operations when you initialize the sequence $a$ to $0$, then apply the $L$-th, $(L+1)$-th, $\dots$, $R$-th operations in order.

Input Format

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

The next $m$ lines each describe one operation in the form $1, l, r, v$ or $2, l, r$.

The next $q$ lines each contain two integers $L, R$, describing one query.

Output Format

Output $q$ lines. Each line contains one integer, the answer to each query in order.

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

64
0
0
36

Hint

For all testdata, $1 \leq l \leq r \leq n$, $1 \leq v \leq n$, $1 \leq L \leq R \leq m$, and $1 \leq n, m, q \leq 5 \times 10^5$.

For $10\%$ of the testdata, $n, m, q \leq 10^2$.

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

For another $10\%$ of the testdata, every operation is a range sum operation.

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

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

For the remaining testdata, there are no special constraints.

Translated by ChatGPT 5