Operation Sequence Query

Given an integer sequence of length \(n\), denoted as \(a_1,\dots,a_n\). You are also given a sequence of \(m\) operations, numbered from 1 to \(m\). There are two types of operations:

• Update operation: Given three integers \(l, r, v\), update all elements \(a_l, a_{l+1}, \dots, a_r\) to \(v\).
• Sum query operation: Given two integers \(l, r\), compute the sum \(\sum_{i=l}^{r} a_i\).

After that, there are \(q\) queries. Each query provides two integers \(L\) and \(R\). For each query, reinitialize the sequence \(a\) to all zeros and then execute the operations numbered \(L, L+1, \dots, R\) in order. For every sum query operation executed, add its result. The answer for the query is the total sum of all these results.

inputFormat

The input format is as follows:

 n m q
 op_1
 op_2
 ...
 op_m
 Q_1
 Q_2
 ...
 Q_q

Where:

• The first line contains three integers \(n\), \(m\), and \(q\), representing the length of the sequence, the number of operations, and the number of queries respectively.
• Each of the next \(m\) lines describes an operation. An update operation is given in the format: 1 l r v, and a sum query operation is given in the format: 2 l r.
• Each of the last \(q\) lines contains two integers \(L\) and \(R\), representing a query. For each query, you need to execute the operations from the \(L\)th to the \(R\)th in order on an array initially filled with zeros.

outputFormat

For each query, output a single line containing one integer: the sum of the results of all sum query operations executed when processing the operations in the given range.

sample

5 4 2
1 1 3 5
2 2 5
1 4 5 2
2 1 5
1 2
2 4

10
4