G. Angel's Salad
time limit per test
10 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a sequence $$$a$$$ of length $$$n$$$ and $$$m$$$ intervals $$$[l_i,r_i]$$$. Initially,$$$a_i=0$$$ for all $$$1 \leq i \leq n$$$.

Here is a sequence $$$b$$$, generated in such a way that all the intervals are expanded into numbers and then put together consecutively.

Formally,$$$b=[a[l_1,...,r_1],a[l_2,...,r_2],...,a[l_m,...,r_m]]$$$.

You have $$$q$$$ queries.Each query is one of the following two types:

1 l r v It means adding $$$v$$$ to all values of $$$a_i$$$ that $$$l\le i\le r$$$($$$1\le l\le r\le n$$$,$$$0\le v\le10^3$$$).

2 l r It means outputing the value of $$$\sum\limits_{i=l}^r b_i$$$( $$$1\le l\le r\le |b|$$$).

Input

The first line has $$$3$$$ integers $$$n$$$, $$$m$$$, $$$q$$$($$$1\le n,m,q\le10^5$$$).

Next $$$m$$$ lines, $$$2$$$ integers per line $$$l_i,r_i(1\leq l_i \leq r_i \leq n)$$$.

Next $$$q$$$ line, $$$3$$$ or $$$4$$$ integers per line,denoting query $$$1$$$ or $$$2$$$.

Output

Only one line,for each query of type $$$2$$$, outputs the value(separated by a space).

Example
Input
4 2 4
1 3
2 4
1 1 2 1
2 2 5
1 2 4 2
2 1 6
Output
2 13
Note

Query $$$1$$$:

Add $$$1$$$ to $$$a_1,a_2$$$.Now $$$a=[1,1,0,0]$$$,$$$b=[1,1,0,1,0,0]$$$.

Query $$$2$$$:

$$$\sum\limits_{i=2}^5 b_i=1+0+1+0=2$$$.

Query $$$3$$$:

Add $$$2$$$ to $$$a_2,a_3,a_4$$$.Now $$$a=[1,3,2,2]$$$,$$$b=[1,3,2,3,2,2]$$$.

Query $$$4$$$:

$$$\sum\limits_{i=1}^6 b_i=1+3+2+3+2+2=13$$$.