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
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        G solver = new G();
        solver.solve(1, in, out);
        out.close();
    }

    static class G {
        int k;
        int[][] val;

        void buildMax(long[][] t, int v, int tl, int tr) {
            if (tl == tr) {
                for (int i = 0; i < 1 << (k - 1); i++) {
                    t[i][v] = val[tl][i];
                }
            } else {
                int tm = (tl + tr) / 2;
                buildMax(t, v * 2, tl, tm);
                buildMax(t, v * 2 + 1, tm + 1, tr);
                for (int i = 0; i < 1 << (k - 1); i++) {
                    t[i][v] = Math.max(t[i][v * 2], t[i][v * 2 + 1]);
                }
            }
        }

        void buildMin(long[][] t, int v, int tl, int tr) {
            if (tl == tr) {
                for (int i = 0; i < 1 << (k - 1); i++) {
                    t[i][v] = val[tl][i];
                }
            } else {
                int tm = (tl + tr) / 2;
                buildMin(t, v * 2, tl, tm);
                buildMin(t, v * 2 + 1, tm + 1, tr);
                for (int i = 0; i < 1 << (k - 1); i++) {
                    t[i][v] = Math.min(t[i][v * 2], t[i][v * 2 + 1]);
                }
            }
        }

        public long max(long[] t, int v, int tl, int tr, int l, int r) {
            if (l > r)
                return Integer.MIN_VALUE;
            if (l == tl && r == tr)
                return t[v];
            int tm = (tl + tr) / 2;
            return Math.max(max(t, v * 2, tl, tm, l, Math.min(r, tm)), max(t, v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r));
        }

        long min(long[] t, int v, int tl, int tr, int l, int r) {
            if (l > r)
                return Integer.MAX_VALUE;
            if (l == tl && r == tr)
                return t[v];
            int tm = (tl + tr) / 2;
            return Math.min(min(t, v * 2, tl, tm, l, Math.min(r, tm)), min(t, v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r));
        }

        void updateMax(long[][] t, int v, int tl, int tr, int pos, int[] new_val) {
            if (tl == tr) {
                for (int i = 0; i < 1 << (k - 1); i++) {
                    t[i][v] = new_val[i];
                }
            } else {
                int tm = (tl + tr) / 2;
                if (pos <= tm)
                    updateMax(t, v * 2, tl, tm, pos, new_val);
                else
                    updateMax(t, v * 2 + 1, tm + 1, tr, pos, new_val);
                for (int i = 0; i < 1 << (k - 1); i++) {
                    t[i][v] = Math.max(t[i][v * 2], t[i][v * 2 + 1]);
                }
            }
        }

        void updateMin(long[][] t, int v, int tl, int tr, int pos, int[] new_val) {
            if (tl == tr) {
                for (int i = 0; i < 1 << (k - 1); i++) {
                    t[i][v] = new_val[i];
                }
            } else {
                int tm = (tl + tr) / 2;
                if (pos <= tm)
                    updateMin(t, v * 2, tl, tm, pos, new_val);
                else
                    updateMin(t, v * 2 + 1, tm + 1, tr, pos, new_val);
                for (int i = 0; i < 1 << (k - 1); i++) {
                    t[i][v] = Math.min(t[i][v * 2], t[i][v * 2 + 1]);
                }
            }
        }

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.ni();
            k = in.ni();
            int[][] p = new int[n][];
            for (int i = 0; i < n; i++) {
                p[i] = in.na(k);
            }

            val = new int[n][1 << (k - 1)];
            for (int mask = 0; mask < 1 << (k - 1); mask++) {
                for (int j = 0; j < k; j++) {
                    if ((mask & (1 << j)) != 0) {
                        for (int i = 0; i < n; i++) {
                            val[i][mask] += p[i][j];
                        }
                    } else {
                        for (int i = 0; i < n; i++) {
                            val[i][mask] -= p[i][j];
                        }
                    }
                }
            }
            int q = in.ni();
            long[][] maxTree = new long[1 << (k - 1)][n * 4];
            long[][] minTree = new long[1 << (k - 1)][n * 4];
            buildMax(maxTree, 1, 0, n - 1);
            buildMin(minTree, 1, 0, n - 1);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < q; i++) {
                int op = in.ni();
                if (op == 1) {
                    int num = in.ni() - 1;
                    int[] np = in.na(k);
                    for (int mask = 0; mask < 1 << (k - 1); mask++) {
                        val[num][mask] = 0;
                        for (int j = 0; j < k; j++) {
                            if ((mask & (1 << j)) != 0) {
                                val[num][mask] += np[j];
                            } else {
                                val[num][mask] -= np[j];
                            }
                        }
                    }
                    updateMax(maxTree, 1, 0, n - 1, num, val[num]);
                    updateMin(minTree, 1, 0, n - 1, num, val[num]);
                } else {
                    long ans = 0;
                    int l = in.ni() - 1, r = in.ni() - 1;
                    for (int j = 0; j < 1 << (k - 1); j++) {
                        long max = max(maxTree[j], 1, 0, n - 1, l, r);
                        long min = min(minTree[j], 1, 0, n - 1, l, r);
                        ans = Math.max(ans, max - min);
                        ans = Math.max(ans, -min + max);
                    }
                    sb.append(ans).append('\n');
                }
            }
            out.print(sb.toString());

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String ns() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(ns());
        }

        public int[] na(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

    }
}

