Description

A $6 \times n$ grid is given, where each cell initially has a non-negative weight. There are two types of operations:

• Change the weight of a cell (the new weight is still non-negative).
• Query the weight of the shortest path between two cells.

Notes and task:

For any cell $P$, its coordinates $(x_P, y_P)$ satisfy $1 \leq x_P \leq 6$, $1 \leq y_P \leq n$. The Manhattan distance between cells $P$ and $Q$ is defined as $|x_P - x_Q| + |y_P - y_Q|$. An ordered sequence of cells $(p_1, p_2, \ldots, p_k)$ is called a path from $p_1$ to $p_k$ if the Manhattan distance between any $p_i$ and $p_{i+1}$ is $1$. Its weight is $d(p_1) + d(p_2) + \cdots + d(p_k)$, where $d(P)$ is the weight of cell $P$. The shortest path between two cells $P$ and $Q$ is a path from $P$ to $Q$ with the minimum total weight.

Input Format

The first line contains an integer $n$. The next $6$ lines each contain $n$ integers; on the $(i+1)$-th line, the $j$-th integer is the initial weight of cell $(i, j)$. Then an integer $Q$ follows, and the next $Q$ lines each describe an operation.

There are two types of operations:

Type $1$: "1 x y c" (without double quotes). Set the weight of cell $(x, y)$ to $c$ ($1 \leq x \leq 6$, $1 \leq y \leq n$, $0 \leq c \leq 10000$).

Type $2$: "2 x_1 y_1 x_2 y_2" (without double quotes). Query the weight of the shortest path between cell $(x_1, y_1)$ and cell $(x_2, y_2)$ ($1 \leq x_1, x_2 \leq 6$, $1 \leq y_1, y_2 \leq n$).

Output Format

For each type $2$ operation, in the order they appear, output one line with one integer: the weight of the shortest path.

5
0 0 1 0 0
0 1 0 1 0
0 2 0 1 0
0 1 1 1 0
0 0 0 0 0
1 1 1 1 1
5
2 1 2 1 4
1 1 1 10000
2 1 2 1 4
1 2 3 10000
2 1 2 3 3

0
1
2

Hint

2024/08/20: Added 3 sets of hack testdata.

Translated by ChatGPT 5