You are given an array a of n points in k-dimensional space. Let the distance between two points a_x and a_y be ∑ _{i = 1}^{k} |a_{x, i} - a_{y, i}| (it is also known as Manhattan distance).

You have to process q queries of the following two types:

  * 1 i b_1 b_2 ... b_k — set i-th element of a to the point (b_1, b_2, ..., b_k);
  * 2 l r — find the maximum distance between two points a_i and a_j, where l ≤ i, j ≤ r.

Input

The first line contains two numbers n and k (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ k ≤ 5) — the number of elements in a and the number of dimensions of the space, respectively.

Then n lines follow, each containing k integers a_{i, 1}, a_{i, 2}, ..., a_{i, k} (-10^6 ≤ a_{i, j} ≤ 10^6) — the coordinates of i-th point.

The next line contains one integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of queries.

Then q lines follow, each denoting a query. There are two types of queries:

  * 1 i b_1 b_2 ... b_k (1 ≤ i ≤ n, -10^6 ≤ b_j ≤ 10^6) — set i-th element of a to the point (b_1, b_2, ..., b_k);
  * 2 l r (1 ≤ l ≤ r ≤ n) — find the maximum distance between two points a_i and a_j, where l ≤ i, j ≤ r.



There is at least one query of the second type.

Output

Print the answer for each query of the second type.

Example

Input


5 2
1 2
2 3
3 4
4 5
5 6
7
2 1 5
2 1 3
2 3 5
1 5 -1 -2
2 1 5
1 4 -1 -2
2 1 5


Output


8
4
4
12
10
// package BigD;

import java.util.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.*;

public class Main {
	private static StringTokenizer ST;
	private static BufferedReader BR;
	private static PrintWriter PW;
	
	private static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    private static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    private static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    private static String next() throws IOException {
        while (ST==null || !ST.hasMoreTokens())
        	ST = new StringTokenizer(BR.readLine());
        return ST.nextToken();
    }
	
	static int INF = (int)1e9;
	static int a[][], A[][];
	static int p, v, no;
	static int qL, qR;
	
	static void build(int L, int R, int o) {
		int M = L + (R - L) / 2;
		if(L == R) a[no][o] = A[no][L];
		else {
			build(L, M, o<<1);
			build(M+1, R, o<<1|1);
			a[no][o] = Math.max(a[no][o<<1], a[no][o<<1|1]);
		}
	}
	
	static void update(int L, int R, int o){
		int M = L + (R - L) / 2;
		if(L == R) a[no][o] = v;
		else{
			if(p <= M) update(L, M, o<<1);
			else update(M+1, R, o<<1|1);
			a[no][o] = Math.max(a[no][o<<1], a[no][o<<1|1]);
		}
	}
	
	static int query(int L, int R, int o){
		int M = L + (R - L) / 2, ans = -INF;
		if(qL <= L && R <= qR) return a[no][o];
		if(qL <= M) ans = Math.max(ans, query(L, M, o<<1));
		if(M + 1 <= qR) ans = Math.max(ans, query(M+1, R, o<<1|1));
		return ans;
	}
	
	public static void main(String[] args) throws IOException {
		BR = new BufferedReader(new InputStreamReader(System.in));
        PW = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        
		int n = nextInt(), m = nextInt();
		
		a = new int[1<<m][n<<2];
		A = new int[1<<m][n+10];
		int[] b = new int[n+10];
		
		for(int i = 1; i <= n; i++) {
			for(int j = 0; j < m; j++)
				b[j] = nextInt();
			
			for(int l = 0; l < (1 << m); l++) {
				int ans = 0;
				for(int j = 0; j < m; j++) {
					if((l & (1 << j)) > 0) {
						ans = ans + b[j];
					}else {
						ans = ans - b[j];
					}
				}
				A[l][i] = ans;
			}
		}
		
		
		for(int l = 0; l < (1 << m); l++) {
			no = l;
			build(1, n, 1);
		}
		
		int q = nextInt();
		
		while(q-- > 0) {
//			System.out.println("ST");
			int op = nextInt();
			if(op == 1) {
				p = nextInt();
				for(int j = 0; j < m; j++) b[j] = nextInt();
				
				for(int l = 0; l < (1 << m); l++) {
					int ans = 0;
					for(int j = 0; j < m; j++) {
						if((l & (1 << j)) > 0) {
							ans = ans + b[j];
						}else {
							ans = ans - b[j];
						}
					}
					no = l;
					v = ans;
					update(1, n, 1);
				}
			} else {
				qL = nextInt(); qR = nextInt();
				int ans = 0;
				for(int l = 0; l < (1 << (m-1)); l++) {
					no = l;
					int x = query(1, n, 1);
					no = (((1 << m) - 1) ^ l);
					int y = query(1, n, 1);
					ans = Math.max(ans, x + y);
//					System.out.println(l + " " + (((1 << m) - 1) ^ l) + " - " + x + " " + y + "Ans = " + ans);
				}
				PW.println(ans);
			}
//			System.out.println("END");
		}
		
		PW.close();
//		out.close();
    }
	
	
}

/*
5 2
1 2
2 3
3 4
4 5
5 6
7
2 1 5
 */
