RishiKumar spends most of his time in solving querying problems. When solving a 2D querying problem he got exhausted and he needs the help of someone. Yes he got!! .. Karthi is in search of his girl and asked Rishi whether he saw his girl on his way. Rishi replied he knew where she has gone but he will disclose the truth if Karthi solve this bloody querying problem. Help Karthi to solve this!!!!

Given two 2D arrays X and Y. Maximum size of X and Y is 500. (500 × 500)

There are 3 operations (Three types of queries)

• 0 x1 y1 x2 y2 - Swaps the contents of the rectangle given by the points (x1, y1) and (x2, y2) of X and Y.
• 1 x1 y1 x2 y2 - Print the sum of all elements in rectangle given by points (x1, y1) and (x2, y2) of the array X.
• 2 x1 y1 x2 y2 - Print the sum of all elements in rectangle given by points (x1, y1) and (x2, y2) of the array Y.

(Points (x1, y1) and (x2, y2) inclusive.)

(x1, y1) - Top left point of the rectangle and (x2, y2) – Bottom right point of the rectangle.

Input

The first line of the input file contains N – Dimension of the array (It is clear that array is square array i.e. length = breadth). The next N lines contains N integers per line separated by space which are the elements of array X. The next N lines contains N integers per line separated by space which are the elements of the array Y. The next line contains the integer Q – the number of queries. Then each of the following Q lines contains the queries as per the above operations.

Constraints

N ≤ 500
0 ≤ X_ij
Y_ij ≤ 10⁶
Q ≤ 10⁵

Array indexing start from [1, 1] to [N, N].

Output

Print the result of each query of type 1 and type 2 line by line.

Example

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

Output:
80
16
80

Warning: Huge I/O, make your I/O fast.