Sequence Operation Queries

Given an integer sequence of length \( n \) represented as \( a_1, a_2, \dots, a_n \). You are also given a sequence of \( m \) operations numbered from 1 to \( m \). Each operation is one of the following:

• Modification operation: Given integers \( l, r, v \), set \( a_l, a_{l+1}, \dots, a_r \) to \( v \).
• Sum query operation: Given integers \( l, r \), compute \( \sum_{i=l}^{r} a_i \).

In addition, there are \( q \) queries. Each query is specified by two integers \( L \) and \( R \). For a given query, you should start with an array \( a \) initialized to zero and then execute operations numbered \( L, L+1, \dots, R \) in order. The answer to the query is defined as the sum of the results from all sum query operations executed during this process.

inputFormat

The first line contains three integers \( n \), \( m \) and \( q \): the length of the sequence, the number of operations, and the number of queries, respectively.

The next \( m \) lines each describe an operation. Each line begins with an integer \( t \):

• If \( t = 1 \), the line contains three more integers \( l, r, v \) (\( 1 \le l \le r \le n \)): a modification operation setting \( a_l, a_{l+1}, \dots, a_r \) to \( v \).
• If \( t = 2 \), the line contains two more integers \( l, r \) (\( 1 \le l \le r \le n \)): a sum query that asks for \( \sum_{i=l}^{r} a_i \).

The next \( q \) lines each contain two integers \( L \) and \( R \) (\( 1 \le L \le R \le m \)). Each such line represents a query on the operations: starting with the sequence initialized to all zeroes, execute operations \( L \) through \( R \) in order, and output the sum of the answers returned by the sum query operations.

outputFormat

For each query, output a single line containing one integer: the total sum of the answers returned by the sum query operations executed in that query.

sample

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

10
8
28