Coin Scattering Challenge

You have run out of money after performing \(n\) ten‐pull draws, so you accepted an invitation from Jin Zhentian to participate in an event. The event takes place on an \(n \times n\) grid and lasts several seconds. At the \(i\)th second, the organizers choose a small rectangular subregion of the grid and scatter coins on every cell within that subregion.

The coin collection process is as follows: Starting from the top‐left cell \((1,1)\), you move to the bottom‐right cell \((n,n)\) following a path where at each step you can only move either down or right. As you pass through a cell, you pick up all the coins present in that cell. For the purpose of the coin collection process, the coin distribution on the grid remains constant (i.e. the coins do not vanish when collected) and the collection is assumed to be completed within 1 second.

You are required to answer three types of queries:

• Type 1: Given a second \(t\) and a rectangular subregion defined by the top-left \((x_1,y_1)\) and bottom-right \((x_2,y_2)\) corners, report the maximum number of coins found in any single cell of that subregion at time \(t\) (after applying all coin scattering events up to second \(t\)).
• Type 2: Given a second \(t\) and a rectangular subregion defined by \((x_1,y_1)\) and \((x_2,y_2)\), report the total number of coins in that subregion at time \(t\).
• Type 3: Given a second \(m\), after performing the coin scattering events up to that second, what is the maximum number of coins you can collect by following a valid path from \((1,1)\) to \((n,n)\) (moving only down or right)?

Each coin scattering event is described by five integers \(x_1\), \(y_1\), \(x_2\), \(y_2\), and \(c\) meaning that, at that particular second, every cell in the subrectangle with top-left \((x_1,y_1)\) and bottom-right \((x_2,y_2)\) receives \(c\) coins.

inputFormat

The input begins with a line containing two integers \(n\) and \(T\) denoting the size of the grid and the number of coin scattering events, respectively.

The next \(T\) lines each contain five integers \(x_1\), \(y_1\), \(x_2\), \(y_2\), and \(c\), describing an event where every cell in the rectangle \((x_1,y_1)\) to \((x_2,y_2)\) gets \(c\) coins added.

This is followed by a line containing a single integer \(Q\), the number of queries. Each of the following \(Q\) lines describes a query in one of the following formats:

• For Type 1 and Type 2 queries: type t x1 y1 x2 y2 where type is 1 (for maximum coin query) or 2 (for sum query), \(t\) is the second (i.e. number of events applied) at which the query is made, and \((x1,y1)\) to \((x2,y2)\) defines the subregion of interest.
• For a Type 3 query: 3 m where \(m\) is the second after which the query is evaluated. The answer is the maximum coins collectable on a valid path from \((1,1)\) to \((n,n)\) in the grid state after applying the first \(m\) events.

outputFormat

For each query, output a single line containing the answer:

• For Type 1 queries, output the maximum coin value in the specified subregion.
• For Type 2 queries, output the sum of coins in the specified subregion.
• For Type 3 queries, output the maximum coins that can be collected along a valid path from \((1,1)\) to \((n,n)\).

sample

3 2
1 1 2 2 5
2 2 3 3 10
3
1 1 1 1 2 2
2 2 1 1 3 3
3 2

5
60
45