Background

Problem Description

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

You are also given a sequence of $m$ operations, numbered from $1$ to $m$. The operations include update operations and range sum operations. An update 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 asks for $\sum\limits_{i=l}^r a_i$.

There are $q$ queries. Each query gives $L,R$ and asks: after initializing the sequence $a$ to $0$, execute operations $L,L+1,\dots,R$ in order, and output the sum of the answers of all range sum operations during this process.

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, in order, representing the answer to each query.

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

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

Constraints: for all testdata, $1\le l\le r\le n$, $1\le v\le n$, $1\le L\le R\le m$, and $1\le n,m,q\le 5\times 10^5$.

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

For another $20\%$ of the testdata, $n,m,q\le 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\le 2\times 10^5$.

For the remaining testdata, there are no special constraints.

Translated by ChatGPT 5