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>
static int k = 1;
static inline int inv(int x) { return ((1 << k) - 1) ^ x; }
static int t[1 << 5][(1 << 18) << 1];
static inline int max(int a, int b) { return a > b ? a : b; }
static inline void init() {
  for (int i = 0; i < (1 << 5); ++i)
    for (int j = 0; j < ((1 << 18) << 1); ++j) t[i][j] = -10000000;
}
static inline void set(int pos, int val[]) {
  for (int sum, mask = 0; mask < (1 << k); ++mask) {
    sum = 0;
    for (int j = 0; j < k; ++j)
      if (mask & (1 << j))
        sum += val[j];
      else
        sum -= val[j];
    t[mask][(1 << 18) + pos] = sum;
  }
  for (int mask = 0; mask < (1 << k); ++mask)
    for (int i = (pos + (1 << 18)) / 2; i; i >>= 1)
      t[mask][i] = max(t[mask][i << 1], t[mask][i << 1 | 1]);
}
static inline int get(int l, int r) {
  static int res[1 << 5], best;
  for (int mask = 0; mask < (1 << k); ++mask) {
    res[mask] = -10000000;
    for (int L = l + (1 << 18), R = r + (1 << 18); L <= R; L >>= 1, R >>= 1) {
      if (L % 2 == 1) res[mask] = max(res[mask], t[mask][L++]);
      if (R % 2 == 0) res[mask] = max(res[mask], t[mask][R--]);
    }
  }
  best = -10000000;
  for (int mask = 0; mask < (1 << k); ++mask)
    best = max(best, res[mask] + res[inv(mask)]);
  return best;
}
int main() {
  int n;
  scanf("%i%i", &n, &k);
  init();
  for (int i = 0; i < n; ++i) {
    static int X[5];
    for (int j = 0; j < k; ++j) scanf("%i", X + j);
    set(i, X);
  }
  int q;
  scanf("%i", &q);
  while (q--) {
    static int t;
    scanf("%i", &t);
    if (t == 1) {
      static int i;
      scanf("%i", &i);
      static int X[5];
      for (int j = 0; j < k; ++j) scanf("%i", X + j);
      set(--i, X);
    } else {
      static int l, r;
      scanf("%i%i", &l, &r);
      printf("%i\n", get(--l, --r));
    }
  }
}
