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 weight remains non-negative after the change). Find the weight of the shortest path between two cells.

Note

The coordinates $(x_P, y_P)$ of any cell $P$ satisfy $1 \le x_P \le 6$ and $1 \le y_P \le 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, \dots, 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$. The weight of this path is $d(p_1) + d(p_2) + \dots + d(p_k)$, where $d(P)$ denotes the weight of cell $P$. The shortest path between two cells $P$ and $Q$ is defined as the path from $P$ to $Q$ with the minimum total weight.

Input

The first line contains an integer $n$. The next 6 lines each contain $n$ integers, where the $j$-th integer on the $(i+1)$-th line represents the initial weight of cell $(i, j)$. The next line contains an integer $Q$, followed by $Q$ lines, each describing an operation. The operations are of the following two types: Operation 1: "1 x y c". This means changing the weight of cell $(x, y)$ to $c$ ($1 \le x \le 6, 1 \le y \le n, 0 \le c \le 10000$). Operation 2: "2 x1 y1 x2 y2". This means querying the weight of the shortest path between cell $(x_1, y_1)$ and cell $(x_2, y_2)$ ($1 \le x_1, x_2 \le 6, 1 \le y_1, y_2 \le n$).

Output

For each operation of type 2, output the weight of the shortest path on a single line, in the order they appear in the input.

Examples

Input 1

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

Output 1

0 
1 
2

Constraints

The scale of the test data is shown in the table below:

Note

The test cases for this problem will be compiled with -O2 optimization.