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;
template <class U, class V>
istream &operator>>(istream &is, pair<U, V> &p) {
  return is >> p.first >> p.second;
}
template <class U, class V>
ostream &operator<<(ostream &os, const pair<U, V> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <
    class Istream, class Container,
    typename std::enable_if<is_same<Istream, istream>::value, int>::type = 0>
Istream &operator>>(Istream &is, Container &container) {
  for (auto &value : container) is >> value;
  return is;
}
template <
    class Ostream, class Container,
    typename std::enable_if<is_same<Ostream, ostream>::value, int>::type = 0>
Ostream &operator<<(Ostream &os, const Container &container) {
  auto _begin = begin(container), _end = end(container);
  for (auto it = _begin; it != _end;)
    os << "{ "[it != _begin] << *it << ",}"[++it == _end];
  return os;
}
namespace io {
template <class... As>
struct last {};
template <class... As>
using last_t = typename last<As...>::type;
template <class A>
struct last<A> {
  using type = A;
};
template <class A, class... As>
struct last<A, As...> {
  using type = typename last<As...>::type;
};
template <class Z>
Z read(Z &) {
  Z z;
  cin >> z;
  return z;
}
template <class A, class... As>
last_t<As...> read(A &a, As &...as) {
  return cin >> a, read(as...);
}
void log_rest() {}
template <class A, class... As>
void log_rest(const A &a, const As &...as) {
  cerr << ", " << a;
  log_rest(as...);
}
template <class A, class... As>
void log(const string &pref, const A &a, const As &...as) {
  cerr << pref << a, log_rest(as...);
}
}  // namespace io
template <class T>
T make_vec(T default_value) {
  return default_value;
}
template <class T, class Arg, class... Args>
auto make_vec(T default_value, Arg size, Args... rest)
    -> vector<decltype(make_vec(default_value, rest...))> {
  auto level = make_vec(default_value, rest...);
  return vector<decltype(level)>(size, level);
}
template <class Xs>
int len(const Xs &xs) {
  return static_cast<int>(xs.size());
}
using i64 = int64_t;
using f80 = long double;
using Str = string;
template <class T = int>
using Vec = vector<T>;
template <class K = int, class H = hash<K>>
using US = unordered_set<K, H>;
template <class K, class V, class H = hash<K>>
using UM = unordered_map<K, V, H>;
template <class U = int, class V = U>
using P = pair<U, V>;
using G = Vec<Vec<int>>;
template <class T, class P>
auto bin_search(T l, T r, P p) -> T {
  for (T m; m = (l + r) / 2, m != l && m != r; (p(m) ? l : r) = m)
    ;
  return l;
}
struct SlowSTree {
  int (*f)(int, int);
  Vec<int> numbers;
  SlowSTree(int (*f)(int, int), const Vec<int> &numbers)
      : f(f), numbers(numbers) {}
  int get(int l, int r) {
    int res = numbers[l];
    for (int i = l + 1; i < r; ++i) {
      res = f(res, numbers[i]);
    }
    return res;
  }
  void set(int i, int x) { numbers[i] = x; }
};
struct STree {
  const int n;
  int (*f)(int, int);
  Vec<int> ns;
  void update(int i) { ns[i] = f(ns[2 * i + 1], ns[2 * i + 2]); }
  void build(const Vec<int> &xs, int i, int il, int ir) {
    if (ir - il == 1) {
      ns[i] = xs[il];
      return;
    }
    int im = (il + ir) / 2;
    build(xs, 2 * i + 1, il, im);
    build(xs, 2 * i + 2, im, ir);
    update(i);
  }
  STree(int (*f)(int, int), const Vec<int> &xs) : n(len(xs)), f(f), ns(4 * n) {
    build(xs, 0, 0, n);
  }
  int get(int l, int r, int i, int il, int ir) {
    if (l <= il && ir <= r) {
      return ns[i];
    }
    int im = (il + ir) / 2;
    if (r <= im) {
      return get(l, r, 2 * i + 1, il, im);
    } else if (im <= l) {
      return get(l, r, 2 * i + 2, im, ir);
    } else {
      return f(get(l, r, 2 * i + 1, il, im), get(l, r, 2 * i + 2, im, ir));
    }
  }
  int get(int l, int r) { return get(l, r, 0, 0, n); }
  void set(int ix, int x, int i, int il, int ir) {
    if (ir - il == 1) {
      ns[i] = x;
      return;
    }
    int im = (il + ir) / 2;
    if (ix < im) {
      set(ix, x, 2 * i + 1, il, im);
    } else {
      set(ix, x, 2 * i + 2, im, ir);
    }
    update(i);
  }
  void set(int ix, int x) { set(ix, x, 0, 0, n); }
};
int min_int(int x, int y) { return min(x, y); }
int max_int(int x, int y) { return max(x, y); }
int main() {
  int n, k = io::read(n, k);
  Vec<Vec<int>> as(n, Vec<int>(k));
  cin >> as;
  auto apply = [k](int mask, const Vec<int> &a) {
    int res = 0;
    for (decltype(k) j = {}; j != k; ++j) {
      if ((mask >> j) & 1) {
        res += a[j];
      } else {
        res -= a[j];
      }
    }
    return res;
  };
  Vec<STree> min_by_mask, max_by_mask;
  for (decltype(1 << (k - 1)) mask = {}; mask != 1 << (k - 1); ++mask) {
    Vec<int> ls(n);
    for (decltype(n) i = {}; i != n; ++i) {
      ls[i] = apply(mask, as[i]);
    }
    while (false) cerr;
    min_by_mask.emplace_back(min_int, ls);
    max_by_mask.emplace_back(max_int, ls);
  }
  while (false) {
    for (decltype(1 << (k - 1)) mask = {}; mask != 1 << (k - 1); ++mask) {
      auto &stree = min_by_mask[mask];
      cerr << "mask: " << mask << " :";
      for (decltype(n) i = {}; i != n; ++i) cerr << " " << stree.get(i, i + 1);
      cerr << endl;
    }
  }
  for (int q = io::read(q); q--;) {
    int t = io::read(t);
    if (t == 1) {
      int i = io::read(i);
      --i;
      Vec<int> a(k);
      cin >> a;
      as[i] = a;
      for (decltype(1 << (k - 1)) mask = {}; mask != 1 << (k - 1); ++mask) {
        min_by_mask[mask].set(i, apply(mask, a));
        max_by_mask[mask].set(i, apply(mask, a));
      }
    } else {
      int l, r = io::read(l, r);
      --l;
      int result = 0;
      for (decltype(1 << (k - 1)) mask = {}; mask != 1 << (k - 1); ++mask) {
        int down = min_by_mask[mask].get(l, r);
        int up = max_by_mask[mask].get(l, r);
        result = max(result, up - down);
      }
      cout << result << '\n';
    }
  }
}
namespace {
auto fast_io = [] {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(8) << fixed;
  cerr << boolalpha << setprecision(4) << fixed;
  return 0;
}();
}
