Shortest Path Queries on a 6×n Grid

Given a grid with 6 rows and n columns (i.e. a 6×n grid), each cell initially contains a non-negative weight. The rows are numbered from 1 to 6 and the columns from 1 to n. Two types of operations are supported:

• Update Operation: Change the weight of a cell to a new non-negative value.
• Query Operation: Given two cells P and Q, compute the weight of the shortest path from P to Q.

Two cells P and Q have coordinates \( (x_P, y_P) \) and \( (x_Q, y_Q) \) with \(1 \le x_P \le 6\) and \(1 \le y_P \le n\). The Manhattan distance between them is defined by \[ |x_P-x_Q|+|y_P-y_Q|. \] A path is an ordered sequence of cells \( (p_1, p_2, \dots, p_k) \) such that each consecutive pair \(p_i, p_{i+1}\) satisfies a Manhattan distance of 1. The weight of a path is the sum of the weights of all cells on the path. The shortest path from one cell to another is defined as the path with the minimum total weight.

You are given the initial grid weights and then a series of operations. For each query operation, output the minimum total weight on a path from the specified start cell to the destination cell.

inputFormat

The input is given in the following format:

n q
\(a_{1,1} a_{1,2} \dots a_{1,n}\)
\(a_{2,1} a_{2,2} \dots a_{2,n}\)
\(a_{3,1} a_{3,2} \dots a_{3,n}\)
\(a_{4,1} a_{4,2} \dots a_{4,n}\)
\(a_{5,1} a_{5,2} \dots a_{5,n}\)
\(a_{6,1} a_{6,2} \dots a_{6,n}\)
q operations

Each operation is in one of the following two forms:

• 1 x y w: Update the weight of the cell at row x and column y to w (\(w \ge 0\)).
• 2 x1 y1 x2 y2: Query the minimum total weight of a path from cell \((x1, y1)\) to cell \((x2, y2)\).

outputFormat

For each query operation (operation type 2), output a single line containing the minimum total weight of a path from the start cell to the destination cell.

sample

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

20
15