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 10\,000~.
• 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	~10\,000~	~20\,000~
5	~10\,000~	~20\,000~
6	~10\,000~	~30\,000~
7	~35\,000~	~30\,000~
8	~50\,000~	~50\,000~
9	~100\,000~	~60\,000~
10	~100\,000~	~100\,000~