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
import java.io.*;
import java.util.*;

public class G implements Runnable{
	public static void main (String[] args) {new Thread(null, new G(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		int n = fs.nextInt();
		int k = fs.nextInt();
		int[][] vs = new int[n][k];
		for(int i = 0; i < n; i++) {
			vs[i] = fs.nextIntArray(k);
		}
		int m = 1 << k;
		ST_[] st = new ST_[m];
		int[] x = new int[n];
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				int sum = 0;
				for(int ii = 0; ii < k; ii++) {
					int mult = i & (1 << ii);
					if(mult > 0) mult = -1;
					else mult = 1;
					sum += mult * vs[j][ii];
				}
				x[j] = sum;
			}
			st[i] = new ST_(n);
			for(int j = 0; j < n; j++) {
				st[i].upd(j, x[j]);
			}
		}
		int q = fs.nextInt();
		int[] it = new int[k];
		while(q-->0) {
			int type = fs.nextInt();
			if(type == 1) {
				int idx = fs.nextInt()-1;
				for(int i = 0; i < k; i++) it[i] = fs.nextInt();
				for(int i = 0; i < m; i++) {
					int sum = 0;
					for(int j = 0; j < k; j++) {
						int mult = i & (1 << j);
						if(mult > 0) mult = -1;
						else mult = 1;
						sum += mult * it[j];
					}
					st[i].upd(idx, sum);
				}
			}
			else {
				int l = fs.nextInt()-1, r = fs.nextInt()-1;
				int res = -(int)2e9;
				for(int i = 0; i < m; i++) {
					res = Math.max(res, st[i].query(l, r, false) - st[i].query(l, r, true));
				}
				out.println(res);
			}
		}

		out.close();
	}
	
	class ST_ {
		int n, oo = (int)2e9;
		int[] min, max;
		ST_(int a) {
			n = 2*a;
			min = new int[n];
			max = new int[n];
		}
		void upd(int idx, int value) {
			idx += n/2;
			min[idx] = value;
			max[idx] = value;
			for(; idx > 1; idx >>= 1) {
				min[idx >> 1] = Math.min(min[idx], min[idx^1]);
				max[idx >> 1] = Math.max(max[idx], max[idx^1]);
			}
		}
		int query(int left, int right, boolean type) {
			int res = type ? oo : -oo;
			left += n/2; right += n/2;
			for(; left <= right; left = (left+1) >> 1, right = (right-1) >> 1) {
				if((left & 1) != 0) {
					if(type) res = Math.min(res, min[left]);
					else res = Math.max(res, max[left]);
				}
				if((right & 1) == 0) {
					if(type) res = Math.min(res, min[right]);
					else res = Math.max(res, max[right]);
				}
			}
			return res;
		}
	}
	
	class ST {
		int n, oo = (int)2e9;
		int[] lo, hi, min, max;
		ST(int a, int[] vs) {
			n = 4*a + 100;
			lo = new int[n];
			hi = new int[n];
			min = new int[n];
			max = new int[n];
			init(0, a-1, 1, vs);
		}
		
		void init(int left, int right, int p, int[] vs) {
			lo[p] = left; hi[p] = right;
			if(left == right) {
				min[p] = vs[left];
				max[p] = vs[left];
				return;
			}
			init(left, (left+right)/2, left(p), vs);
			init((left+right)/2+1, right, right(p), vs);
			max[p] = Math.max(max[left(p)], max[right(p)]);
			min[p] = Math.min(min[left(p)], min[right(p)]);
		}
		
		void upd(int idx, int val, int p) {
			if(lo[p] == hi[p] && lo[p] == idx) {
				min[p] = val;
				max[p] = val;
				return;
			}
			if(idx < lo[p] || idx > hi[p]) return;
			if(lo[left(p)] <= idx && idx <= hi[left(p)])
				upd(idx, val, left(p));
			else
				upd(idx, val, right(p));
			max[p] = Math.max(max[left(p)], max[right(p)]);
			min[p] = Math.min(min[left(p)], min[right(p)]);
		}
		
		int val(int left, int right, int p, boolean type) {
			if(right < lo[p] || left > hi[p]) return type ? oo : -oo;
			if(left <= lo[p] && hi[p] <= right) {
				if(type) return min[p];
				return max[p];
			}
			int v1 = val(left, right, left(p), type);
			int v2 = val(left, right, right(p), type);
			if(type) return Math.min(v1, v2);
			return Math.max(v1, v2);
		}
		
		int left(int p) { return p << 1; }
		int right(int p) { return (p << 1) + 1; }
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}