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 namespace std;
struct Point {
  int dim;
  int val[5];
};
struct Node {
  int mx, mn;
};
struct SegmentTree {
  int operationMask;
  int n;
  Node data[1 << 20];
  inline int lc(int x) { return x * 2; }
  inline int rc(int x) { return x * 2 + 1; }
  inline int mid(int x, int y) { return (x + y) / 2; }
  inline void pull(int idx) {
    data[idx].mx = max(data[lc(idx)].mx, data[rc(idx)].mx);
    data[idx].mn = min(data[lc(idx)].mn, data[rc(idx)].mn);
  }
  void init(int _n, Point points[]) {
    n = _n;
    init(points, 1, 0, n);
  }
  int getVal(const Point &point) {
    int val = 0;
    for (int i = 0; i < point.dim; i++) {
      if ((operationMask >> i) & 1)
        val += 1 * point.val[i];
      else
        val += -1 * point.val[i];
    }
    return val;
  }
  void init(Point points[], int idx, int lb, int rb) {
    if (rb - lb == 1) {
      int val = getVal(points[lb]);
      data[idx].mx = data[idx].mn = val;
      return;
    }
    int m = mid(lb, rb);
    init(points, lc(idx), lb, m);
    init(points, rc(idx), m, rb);
    pull(idx);
  }
  void update(int who, int idx, int lb, int rb, const Point &newPoint) {
    if (rb - lb == 1 && who == lb) {
      int val = getVal(newPoint);
      data[idx].mx = data[idx].mn = val;
      return;
    }
    if (who < mid(lb, rb))
      update(who, lc(idx), lb, mid(lb, rb), newPoint);
    else
      update(who, rc(idx), mid(lb, rb), rb, newPoint);
    pull(idx);
  }
  void update(int who, const Point &newPoint) {
    update(who, 1, 0, n, newPoint);
  }
  int query(int l, int r, int idx, int lb, int rb, bool isGetMin) {
    if (rb <= l || r <= lb) return isGetMin ? INT_MAX : INT_MIN;
    if (l <= lb && rb <= r) {
      if (isGetMin) return data[idx].mn;
      return data[idx].mx;
    }
    int m = mid(lb, rb);
    int ret1 = query(l, r, lc(idx), lb, m, isGetMin);
    int ret2 = query(l, r, rc(idx), m, rb, isGetMin);
    if (isGetMin) return min(ret1, ret2);
    return max(ret1, ret2);
  }
  int getMin(int l, int r) { return query(l, r, 1, 0, n, true); }
  int getMax(int l, int r) { return query(l, r, 1, 0, n, false); }
  void print() {
    printf("mask %d\n", operationMask);
    for (int i = 1; i <= 4 * n; i++)
      printf("%d -> %d %d\n", i, data[i].mx, data[i].mn);
  }
} segmentTree[32];
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  Point points[n];
  for (int i = 0; i < n; i++) {
    points[i].dim = k;
    for (int j = 0; j < k; j++) scanf("%d", &points[i].val[j]);
  }
  for (int i = 0; i < 32; i++) {
    segmentTree[i].operationMask = i;
    segmentTree[i].init(n, points);
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int command;
    scanf("%d", &command);
    if (command == 1) {
      int which;
      scanf("%d", &which);
      which--;
      Point newPoint;
      for (int i = 0; i < k; i++) scanf("%d", &newPoint.val[i]);
      newPoint.dim = k;
      for (int i = 0; i < 32; i++) {
        segmentTree[i].update(which, newPoint);
      }
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      l--;
      int mx = 0;
      for (int i = 0; i < 32; i++) {
        int res =
            abs(segmentTree[i].getMax(l, r) - segmentTree[i].getMin(l, r));
        mx = max(mx, res);
      }
      printf("%d\n", mx);
    }
  }
  return 0;
}
