You are given a $6\times n$ grid, where each lattice point is labelled by a (not necessarily distinct) non-negative integer. There are two types of operations:

1. Change the label of a lattice point to another non-negative integer.
2. Find the shortest path between two lattice points.

Here the length of a path is defined as the sum of labels of all lattice points the path passes through, and two lattice points are adjacent if they have Manhattan distance 1 (i.e. $(x_1,y_1)\sim (x_2,y_2)$ if $|x_1-x_2|+|y_1-y_2|=1$).

Input Specification

The first line of input will contain a single integer, $n$.
The next 6 lines will contain $n$ integers each, where the $j$th integer in the $(i+1)$th row is the label of $(i,j)$.
The following line will contain a single integer, $Q$, the number of operations.
The operations will be one of the following:

• 1 x y c: The label of $(x,y)$ is changed to $c$, where $1\le x\le 6$, $1\le y\le n$, $0\le c\le 10000$.
• 2 x1 y1 x2 y2: Output the length of the shortest path between $(x_1,y_1)$ and $(x_2,y_2)$, as defined above, where $1\le x_1,x_2\le 6$, $1\le y_1,y_2\le n$.

Output Specification

For each type 2 operation, output the length of the shortest path between $(x_1,y_1)$ and $(x_2,y_2)$ on a new line.

Sample Input

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

Sample Output

0
1
2

Constraints

Case	$n$	$Q$
1	$10$	$20$
2	$100$	$200$
3	$1000$	$2000$
4	$10000$	$20000$
5	$10000$	$20000$
6	$10000$	$30000$
7	$35000$	$30000$
8	$50000$	$50000$
9	$100000$	$60000$
10	$100000$	$100000$