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.*;
import java.util.StringTokenizer;

/**
 * CodeForces
 * G. Multidimensional Queries
 */
public class Main {

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        Task task = new Task();
        task.solve(in, out);
        out.close();
    }

    static class Task {
        int n, k;
        int[][] data;
        int[][] max;
        int[][] min;


        public void cal(int id, int index) {
            int temp;
            for (int s = 0; s < (1 << k); s++) {
                temp = 0;
                for (int i = 0; i < k; i++) {
                    temp += ((1 << i) & s) > 0 ? data[id][i] : -data[id][i];
                }
                max[index][s] = min[index][s] = temp;
            }
        }

        void build(int l, int r, int index) {
            if (l == r) {
                cal(l, index);
                return;
            }
            int mid = (l + r) >> 1;
            build(l, mid, index << 1);
            build(mid + 1, r, index << 1 | 1);
            push(index);
        }

        public void push(int index) {
            for (int s = 0; s < (1 << k); s++) {
                max[index][s] = Math.max(max[index << 1][s], max[index << 1 | 1][s]);
                min[index][s] = Math.min(min[index << 1][s], min[index << 1 | 1][s]);
            }
        }

        void update(int id, int l, int r, int index) {
            if (l == r) {
                cal(id, index);
                return;
            }

            int mid = (l + r) >> 1;
            if (id <= mid) {
                update(id, l, mid, index << 1);
            } else {
                update(id, mid + 1, r, index << 1 | 1);
            }
            push(index);
        }

        void qry(int L, int R, int l, int r, int index, int s, int[] mm) {
            if (L <= l && r <= R) {
                mm[0] = Math.max(mm[0], max[index][s]);
                mm[1] = Math.min(mm[1], min[index][s]);
                return;
            }
            int mid = (l + r) >> 1;
            if (R > mid) {
                qry(L, R, mid + 1, r, index << 1 | 1, s, mm);
            }
            if (L <= mid) {
                qry(L, R, l, mid, index << 1, s, mm);
            }
        }

        int query(int L, int R) {
            int ans = 0;
            int[] mm = new int[2];
            for (int s = 0; s < (1 << k); s++) {
                mm[0] = Integer.MIN_VALUE;
                mm[1] = Integer.MAX_VALUE;
                qry(L, R, 1, n, 1, s, mm);
                ans = Math.max(mm[0] - mm[1], ans);
            }
            return ans;
        }


        public void solve(InputReader in, PrintWriter out) {
            this.n = in.nextInt();
            this.k = in.nextInt();
            this.data = new int[n + 1][k];
            this.max = new int[(n << 2) + 1][1 << k];
            this.min = new int[(n << 2) + 1][1 << k];
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < k; j++) {
                    data[i][j] = in.nextInt();
                }
            }
            build(1, n, 1);
            int query;
            query = in.nextInt();
            int type, id, l, r;
            while (query-- > 0) {
                type = in.nextInt();
                switch (type) {
                    case 1:
                        id = in.nextInt();
                        for (int i = 0; i < k; i++) {
                            this.data[id][i] = in.nextInt();
                        }
                        update(id, 1, n, 1);
                        break;
                    case 2:
                        l = in.nextInt();
                        r = in.nextInt();
                        out.println(query(l, r));
                        break;
                }
            }
        }
    }
}
