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 CF1093G {
	static int[][] max, min, aa;
	static int[] bb;
	static int b;
	static int convert(int i, int k) {
		int a = 0;
		for (int j = 0; j < k; j++)
			a += (b & 1 << j) > 0 ? bb[j] : -bb[j];
		return a;
	}
	static void build(int k, int l, int r) {
		if (r - l == 1) {
			max[b][k] = min[b][k] = aa[b][l];
			return;
		}
		int m = (l + r) / 2;
		int k1 = k + k + 1, k2 = k + k + 2;
		build(k1, l, m);
		build(k2, m, r);
		max[b][k] = Math.max(max[b][k1], max[b][k2]);
		min[b][k] = Math.min(min[b][k1], min[b][k2]);
	}
	static void update(int k, int l, int r, int i, int a) {
		if (r - l == 1) {
			max[b][k] = min[b][k] = a;
			return;
		}
		int m = (l + r) / 2;
		int k1 = k + k + 1, k2 = k + k + 2;
		if (i < m)
			update(k1, l, m, i, a);
		else
			update(k2, m, r, i, a);
		max[b][k] = Math.max(max[b][k1], max[b][k2]);
		min[b][k] = Math.min(min[b][k1], min[b][k2]);
	}
	static int ql, qr;
	static int query(int k, int l, int r, boolean max_min) {
		if (qr <= l || r <= ql)
			return max_min ? Integer.MIN_VALUE : Integer.MAX_VALUE;
		if (ql <= l && r <= qr)
			return max_min ? max[b][k] : min[b][k];
		int m = (l + r) / 2;
		int a1 = query(k + k + 1, l, m, max_min);
		int a2 = query(k + k + 2, m, r, max_min);
		return max_min ? Math.max(a1, a2) : Math.min(a1, a2);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int k_ = 1 << k - 1;
		bb = new int[k];
		aa = new int[k_][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < k; j++)
				bb[j] = Integer.parseInt(st.nextToken());
			for (b = 0; b < k_; b++)
				aa[b][i] = convert(i, k);
		}
		int m = 1;
		while (m < n)
			m *= 2;
		m *= 2;
		max = new int[k_][m];
		min = new int[k_][m];
		for (b = 0; b < k_; b++)
			build(0, 0, n);
		int q = Integer.parseInt(br.readLine());
		while (q-- > 0) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
			if (type == 1) {
				int i = Integer.parseInt(st.nextToken()) - 1;
				for (int j = 0; j < k; j++)
					bb[j] = Integer.parseInt(st.nextToken());
				for (b = 0; b < k_; b++)
					update(0, 0, n, i, convert(i, k));
			} else {
				ql = Integer.parseInt(st.nextToken()) - 1;
				qr = Integer.parseInt(st.nextToken());
				int ans = 0;
				for (b = 0; b < k_; b++)
					ans = Math.max(ans, query(0, 0, n, true) - query(0, 0, n, false));
				pw.println(ans);
			}
		}
		pw.close();
	}
}
