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 _nl {
} nl;
template <typename N, typename L, int flags>
struct seg_tree_alice {
  vector<N> data;
  int sz;
  seg_tree_alice(int n) {
    sz = 1 << (32 - __builtin_clz(n - 1));
    data.resize(sz * 2);
  }
  void init(int ix, L value) { data[sz + ix].value = value; }
  void build() {
    for (int i = sz - 1; i > 0; i--)
      data[i].sum(data[i * 2], data[i * 2 + 1], 0);
  }
  void push(N &n, N &lc, N &rc) {
    if constexpr ((flags & 1) == 1) {
      if constexpr ((flags & 2) == 2) {
        if (n.tag) {
          lc.lazy = n.lazy;
          lc.tag = true;
          rc.lazy = n.lazy;
          rc.tag = true;
          n.tag = false;
        } else {
          lc.lazy = lc.lazy + n.lazy;
          rc.lazy = rc.lazy + n.lazy;
        }
      } else {
        lc.lazy = lc.lazy + n.lazy;
        rc.lazy = rc.lazy + n.lazy;
      }
      n.lazy = L();
    }
  }
  void set0(int l, int r, int l0, int r0, int ix, L value) {
    auto &n = data[ix];
    if (l == l0 && r == r0) {
      if constexpr ((flags & 4) == 4) {
        n.lazy = value;
      } else {
        n.value = value;
      }
      if constexpr ((flags & 2) == 2) n.tag = true;
    } else {
      auto &lc = data[ix * 2];
      auto &rc = data[ix * 2 + 1];
      int m0 = (l0 + r0) / 2;
      push(n, lc, rc);
      if (l < m0) set0(l, min(m0, r), l0, m0, ix * 2, value);
      if (r > m0) set0(max(m0, l), r, m0, r0, ix * 2 + 1, value);
      n.sum(lc, rc, m0 - l0);
    }
  }
  void update0(int l, int r, int l0, int r0, int ix, L value) {
    auto &n = data[ix];
    if (l == l0 && r == r0) {
      if constexpr ((flags & 4) == 4) {
        n.lazy = n.lazy + value;
      } else {
        n.value = n.value + value;
      }
    } else {
      auto &lc = data[ix * 2];
      auto &rc = data[ix * 2 + 1];
      int m0 = (l0 + r0) / 2;
      push(n, lc, rc);
      if (l < m0) update0(l, min(m0, r), l0, m0, ix * 2, value);
      if (r > m0) update0(max(m0, l), r, m0, r0, ix * 2 + 1, value);
      n.sum(lc, rc, m0 - l0);
    }
  }
  void query0(int l, int r, int l0, int r0, int ix, N &target, bool &v) {
    auto &n = data[ix];
    if (l == l0 && r == r0) {
      if (v)
        target.qsum(n);
      else
        target = n;
      v = true;
    } else {
      auto &lc = data[ix * 2];
      auto &rc = data[ix * 2 + 1];
      push(n, lc, rc);
      int m0 = (l0 + r0) / 2;
      if (l < m0) query0(l, min(m0, r), l0, m0, ix * 2, target, v);
      if (r > m0) query0(max(m0, l), r, m0, r0, ix * 2 + 1, target, v);
    }
  }
  void set(int l, int r, L value) { set0(l, r, 0, sz, 1, value); }
  void update(int l, int r, L value) { update0(l, r, 0, sz, 1, value); }
  N query(int l, int r) {
    auto res = N();
    bool v = false;
    query0(l, r, 0, sz, 1, res, v);
    return res;
  }
};
bool _ns = 0;
template <typename T>
void _p(const T &_) {
  if constexpr (is_same<T, _nl>()) {
    cout << "\n";
    _ns = 0;
  } else {
    if (_ns) cout << " ";
    cout << _;
    _ns = 1;
  }
}
template <typename... T>
void out(const T &..._) {
  (_p(_), ...);
}
int ii() {
  int _;
  cin >> _;
  return _;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  static int buf[5];
  for (auto i = 0; i < 5; i++) buf[i] = 0;
  struct xpnt {
    int b[32];
    void join(xpnt &l, xpnt &r) {
      for (auto i = 0; i < 32; i++) b[i] = max(l.b[i], r.b[i]);
    }
    xpnt() {}
    xpnt(int k) {
      for (auto i = 0; i < k; i++) buf[i] = ii();
      for (auto i = 0; i < 32; i++) {
        int s = 0;
        for (int j = 0; j < 5; j++) {
          int bit = 1 << j;
          s += (i & bit) ? buf[j] : -buf[j];
        }
        b[i] = s;
      }
    }
    int ans() {
      int v = 0;
      for (auto i = 0; i < 32; i++) {
        v = max(v, b[i] + b[i ^ 31]);
      }
      return v;
    }
  };
  struct node {
    xpnt value;
    void sum(node &l, node &r, int sz) { value.join(l.value, r.value); }
    void qsum(node &n) { value.join(value, n.value); }
  };
  auto n = ii();
  auto k = ii();
  seg_tree_alice<node, xpnt, 0> st(n);
  for (auto i = 0; i < n; i++) {
    st.init(i, xpnt(k));
  }
  st.build();
  auto q = ii();
  for (auto i = 0; i < q; i++) {
    int type = ii();
    if (type == 1) {
      int ix = ii() - 1;
      st.set(ix, ix + 1, xpnt(k));
    } else {
      int l = ii() - 1;
      int r = ii();
      out(st.query(l, r).value.ans(), nl);
    }
  }
  return 0;
}
