Storage System Operations

You are given a storage system with n sections and a timeline of operations. Two types of operations are supported:

• Update Operation: "1 t s d". At time t, update section s with the data value d. If an update already exists for that section at that time, overwrite it.
• Query Operation: "2 t1 t2 s1 s2". Query the sum of all data values from sections in the range [s1, s2] and for update times in the interval [t1, t2].

Your task is to implement the storage system that processes a sequence of these operations. When a query is encountered, output the query result on a new line.

The formulas used in the problem are given below in \( \LaTeX \) format:

Update: For an operation 1 t s d, set \( A_{s,t} = d \).

Query: For an operation 2 t_1 t_2 s_1 s_2, compute \( Q = \sum_{s=s_1}^{s_2} \sum_{t=t_1}^{t_2} A_{s,t} \).

inputFormat

Input is read from standard input (stdin) with the following format:

n q
operation_1
operation_2
...
operation_q

Here, n is the number of sections, q is the number of operations. Each following line represents an operation in one of the two formats:

• Update: 1 t s d
• Query: 2 t1 t2 s1 s2

outputFormat

For every query operation (operations starting with 2), output the computed sum on a new line to standard output (stdout).

## sample

8 5
1 2 3 100
1 4 3 200
1 5 2 150
2 3 5 2 3
1 4 2 50

350

</p>