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 D {

	static int n, k;
	static int INF = (int) 1e9;

	static int[] lg, val;
	static int[] pre = new int[1 << 5];

	static int getVal(int msk) {
		int ans = 0;
		if (msk == 0) {
			for (int x : val)
				ans -= x;
			return pre[msk] = ans;
		}
		int one = msk & -msk;
		ans = pre[msk - one] + 2 * val[lg[one]];
		return pre[msk] = ans;

	}

	static class pair {
		int min, max;

		pair() {
			min = INF;
			max = -INF;
		}

		pair(int a, int b) {
			max = a;
			min = b;
		}

		pair merge(pair p) {
			return new pair(Math.max(p.max, max), Math.min(min, p.min));
		}
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		n = sc.nextInt();
		k = sc.nextInt();
		lg = new int[1 << k];
		for (int i = 0; i < k; i++)
			lg[1 << i] = i;
		SegmentTree[] max = new SegmentTree[1 << k];
//		min = new SegmentTree[1 << k];
		int[][] a = new int[1 << k][n];

		val = new int[k];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < k; j++)
				val[j] = sc.nextInt();
			for (int msk = 0; msk < 1 << k; msk++) {
				int curr = getVal(msk);
//				max[msk].update(i, curr);
				a[msk][i] = curr;

			}
		}
		for (int i = 0; i < 1 << k; i++) {
			max[i] = new SegmentTree(a[i]);
//			min[i] = new SegmentTree();

		}
		int q = sc.nextInt();
		while (q-- > 0) {
			int t = sc.nextInt();
			if (t == 1) {
				int idx = sc.nextInt() - 1;
				for (int j = 0; j < k; j++)
					val[j] = sc.nextInt();
				for (int msk = 0; msk < 1 << k; msk++) {
					int curr = getVal(msk);
					max[msk].update(idx, curr);

				}

			} else {
				int l = sc.nextInt() - 1, r = sc.nextInt() - 1;
				int ans = -INF;
				for (int msk = 0; msk < 1 << k; msk++) {
					pair p = max[msk].query(l, r);
					int currMin = p.min;
					int currMax = p.max;
					ans = Math.max(ans, currMax - currMin);
				}
				out.println(ans);

			}
		}
		out.close();

	}

	static class SegmentTree {
		int[] max, min, a;

		SegmentTree(int[] a) {
			max = new int[4 * n];
			min = new int[4 * n];
			this.a = a;
			build(1, 0, n - 1);
		}

		void build(int node, int tl, int tr) {
			if (tl == tr) {
				max[node] = a[tl];
				min[node] = a[tl];
			} else {
				int mid = tl + tr >> 1, left = node << 1, right = left | 1;

				build(left, tl, mid);

				build(right, mid + 1, tr);
				max[node] = Math.max(max[left], max[right]);
				min[node] = Math.min(min[left], min[right]);

			}
		}

		void update(int idx, int v) {
			update(1, 0, n - 1, idx, v);
		}

		void update(int node, int tl, int tr, int idx, int v) {
			if (tl == tr) {
				max[node] = v;
				min[node] = v;
			} else {
				int mid = tl + tr >> 1, left = node << 1, right = left | 1;
				if (idx <= mid)
					update(left, tl, mid, idx, v);
				else
					update(right, mid + 1, tr, idx, v);
				max[node] = Math.max(max[left], max[right]);
				min[node] = Math.min(min[left], min[right]);

			}
		}

		pair query(int l, int r) {
			return query(1, 0, n - 1, l, r);
		}

		pair query(int node, int tl, int tr, int l, int r) {
			if (r < tl || tr < l)
				return new pair();
			if (tl >= l && tr <= r)
				return new pair(max[node], min[node]);
			int mid = tl + tr >> 1, left = node << 1, right = left | 1;

			return query(left, tl, mid, l, r).merge(query(right, mid + 1, tr, l, r));

		}

//		int min(int l, int r) {
//			return min(1, 0, n - 1, l, r);
//		}
//
//		int min(int node, int tl, int tr, int l, int r) {
//			if (r < tl || tr < l)
//				return INF;
//			if (tl >= l && tr <= r)
//				return min[node];
//			int mid = tl + tr >> 1, left = node << 1, right = left | 1;
//
//			return Math.min(min(left, tl, mid, l, r), min(right, mid + 1, tr, l, r));
//
//		}
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		boolean ready() throws IOException {
			return br.ready();
		}

	}

	static void sort(int[] a) {
		shuffle(a);
		Arrays.sort(a);
	}

	static void shuffle(int[] a) {
		int n = a.length;
		Random rand = new Random();
		for (int i = 0; i < n; i++) {
			int tmpIdx = rand.nextInt(n);
			int tmp = a[i];
			a[i] = a[tmpIdx];
			a[tmpIdx] = tmp;
		}
	}

}