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;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
struct seg_tree {
  int S;
  vector<T> value;
  seg_tree<T>(int S) : S(S) { value.resize(2 * S); }
  void rebuild() {
    for (int i = S - 1; i > 0; i--) value[i] = value[2 * i] + value[2 * i + 1];
  }
  void upd(int i, T v) {
    i += S;
    value[i] = v;
    while (i > 1) {
      i /= 2;
      value[i] = value[2 * i] + value[2 * i + 1];
    }
  }
  T query(int i, int j) {
    T res_left, res_right;
    for (i += S, j += S; i <= j; i /= 2, j /= 2) {
      if ((i & 1) == 1) res_left = res_left + value[i++];
      if ((j & 1) == 0) res_right = value[j--] + res_right;
    }
    return res_left + res_right;
  }
};
struct node {
  int lo = INT_MAX, hi = INT_MIN;
  node() {}
  node(int v) { lo = v, hi = v; }
  node(int l, int h) { lo = l, hi = h; }
  node operator+(const node& o) const {
    return node(min(lo, o.lo), max(hi, o.hi));
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int N, K;
  cin >> N >> K;
  vector<seg_tree<node>> st(16, seg_tree<node>(N));
  auto set = [&](int i, array<int, 5> v) {
    for (int m = 0; m < 16; m++) {
      int t = v[0];
      for (int i = 0; i < 4; i++) {
        if (m & (1 << i))
          t += v[i + 1];
        else
          t -= v[i + 1];
      }
      st[m].upd(i, node(t));
    }
  };
  array<int, 5> pt;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < K; j++) cin >> pt[j];
    set(i, pt);
  }
  int Q, t, i, l, r;
  cin >> Q;
  for (int q = 0; q < Q; q++) {
    cin >> t;
    if (t == 1) {
      cin >> i;
      for (int j = 0; j < K; j++) cin >> pt[j];
      set(i - 1, pt);
    } else {
      int ans = 0;
      cin >> l >> r;
      for (int m = 0; m < 16; m++) {
        node res = st[m].query(l - 1, r - 1);
        ans = max(ans, res.hi - res.lo);
      }
      cout << ans << "\n";
    }
  }
  return 0;
}
