Taco Grid Path Queries

You are given a grid with n rows and m columns, where each cell contains a non-negative integer. The grid is 1-indexed. You need to process a series of queries on this grid. There are two types of queries:

• Type 1 query: 1 x1 y1 x2 y2. In this query, you are asked to compute the minimum path sum from cell (x1, y1) to cell (x2, y2) by only moving either right or down. The minimum path sum is given by the recurrence formula in LaTeX: $$dp[i][j] = grid[i][j] + \min(dp[i-1][j], dp[i][j-1])$$ with appropriate boundary conditions.
• Type 2 query: 2 x y v. In this query, update the value at cell (x, y) of the grid to v.

You are to process all queries sequentially. For every Type 1 query, output the computed minimum path sum on a new line.

inputFormat

The first line contains two space-separated integers n and m indicating the grid dimensions.

The next n lines each contain m space-separated integers describing the grid.

The following line contains an integer Q, the number of queries.

Each of the next Q lines contains a query in one of the two formats:

• 1 x1 y1 x2 y2 for Type 1 queries.
• 2 x y v for Type 2 queries.

All indices are 1-indexed.

outputFormat

For each Type 1 query, output the minimum path sum on a separate line. No output is produced for Type 2 queries.

## sample

3 3
1 2 3
4 5 6
7 8 9
3
1 1 1 3 3
2 2 2 1
1 1 1 3 3

21
19

</p>