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
#include <bits/stdc++.h>
using std::max;
using std::min;
using std::swap;
using std::vector;
const int K = 33;
const int N = 2e5 + 5;
int n, k, m, maxn, val[N][6];
struct Node {
  int a[K];
  Node() { memset(a, 0xcf, sizeof a); }
  friend Node operator+(Node x, Node y) {
    Node z;
    for (int i = 0; i <= maxn; i++) z.a[i] = max(x.a[i], y.a[i]);
    return z;
  }
} sum[N << 2];
int getint() {
  int X = 0, w = 0;
  char ch = getchar();
  while (!isdigit(ch)) w |= ch == '-', ch = getchar();
  while (isdigit(ch)) X = X * 10 + ch - 48, ch = getchar();
  if (w) return -X;
  return X;
}
void pushup(int x) { sum[x] = sum[x << 1] + sum[x << 1 | 1]; }
void build(int x, int l, int r) {
  if (l == r) {
    for (int i = 0; i <= maxn; i++) {
      sum[x].a[i] = 0;
      for (int j = 0; j < k; j++) {
        if (i >> j & 1)
          sum[x].a[i] += val[l][j];
        else
          sum[x].a[i] -= val[l][j];
      }
    }
    return;
  }
  int mid = l + r >> 1;
  build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  pushup(x);
}
void modify(int x, int l, int r, int ql) {
  if (l == r) {
    for (int i = 0; i <= maxn; i++) {
      sum[x].a[i] = 0;
      for (int j = 0; j < k; j++) {
        if (i >> j & 1)
          sum[x].a[i] += val[l][j];
        else
          sum[x].a[i] -= val[l][j];
      }
    }
    return;
  }
  int mid = l + r >> 1;
  ql <= mid ? modify(x << 1, l, mid, ql) : modify(x << 1 | 1, mid + 1, r, ql);
  pushup(x);
}
Node query(int x, int l, int r, int ql, int qr) {
  if (ql <= l and r <= qr) return sum[x];
  int mid = l + r >> 1;
  Node ans;
  if (ql <= mid) ans = ans + query(x << 1, l, mid, ql, qr);
  if (mid < qr) ans = ans + query(x << 1 | 1, mid + 1, r, ql, qr);
  return ans;
}
signed main() {
  n = getint(), k = getint();
  maxn = (1 << k) - 1;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < k; j++) val[i][j] = getint();
  build(1, 1, n);
  m = getint();
  while (m--) {
    if (getint() == 1) {
      int pos = getint();
      for (int i = 0; i < k; i++) val[pos][i] = getint();
      modify(1, 1, n, pos);
    } else {
      int l = getint(), r = getint();
      Node ans = query(1, 1, n, l, r);
      int ppp = -1e9;
      for (int i = 0; i <= maxn; i++)
        ppp = max(ppp, ans.a[i] + ans.a[i ^ maxn]);
      printf("%d\n", ppp);
    }
  }
  return 0;
}
