Let us call the query of type 1 l r x an addition query and that of type 2 i x an assignment query.

Suppose that we are asked to find the value of \((i, j)\) in the \(q\)-th query. The only assignment query for the \(i\)-th row we have to take into account is the latest one. Suppose that that assignment query is the \(q\)-th query and it asks to assign \(x\), then the desired value is:

• \(x\) plus the sum of values added to the \(j\)-th column in the \(q'+1\)-th, \(\dots\), \(q\)-th queries.

Let \(S_{k, j}\) be the values added to the \(j\)-th column in the \(1\)-st, \(2\)-nd, \(\dots\), \(k\)-th query; then the answer is \(x + S_{q, j} - S_{q', j}\).

Now we have boiled down the problem to the problem of finding \(S_{k, j}\). Now, we want to solve the following task.

• First, initialize a sequence \(S\) with \(S = (0, \dots, 0)\).
• Process queries of the following format.
  • Add \(x\) to \(S_l, \dots, S_r\).
  • Output \(S_j\).

Instead of \(S\) itself, we can consider their differences, so that the task above is rephrased as follows:

• First, initialize the sequence \(S'\) with \(S' = (0, \dots, 0)\).
• Process queries of the following format.
  • Add \(x\) to \(S'_l\) and \(-x\) to \(S'_{r+1}\).
  • Output \(S'_1 + \dots + S'_j\).

This can be solved efficiently with a data structure called Fenwick Tree. It is convenient to use atcoer::fenwick_tree in AtCoder Library. The overall time complexity is \(O(N + M + Q \log M)\).

Sample code (C++)