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
/**
 * Created by Aminul on 12/15/2018.
 */

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

import static java.lang.Math.max;

public class G_int_2 {
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        int n = in.nextInt(), d = in.nextInt(), L = 1 << d;
        preCal(d, n);

        int point[] = new int[d];
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < d; j++) {
                point[j] = in.nextInt();
            }
            update(L, d, i, point);
        }

        int q = in.nextInt();
        for (int i = 0; i < q; i++) {
            int tp = in.nextInt();
            if(tp == 1) {
                int pos = in.nextInt();
                for(int j = 0; j < d; j++) {
                    point[j] = in.nextInt();
                }
                update(L, d, pos, point);
            }
            else {
                int l = in.nextInt(), r = in.nextInt();
                pw.println(query(L, l, r));
            }
        }

        pw.close();
    }

    static SegTree[] segTrees;
    static void update(int L, int d, int pos,  int point[]) {
        for(int j = 0; j < L; j++){
            int sum = 0;
            for(int k = 0; k < d; k++){
                if(check(j, k)){
                    sum += point[k];
                }
                else{
                    sum -= point[k];
                }
            }
            segTrees[j].update(pos, sum);
        }
    }

    static long query(int L, int l, int r) {
        long max = Long.MIN_VALUE;
        for (int i = 0; i < L; i++) {
            long s = segTrees[i].query(l, r) + segTrees[reverse[i]].query(l, r);
            max = max(max, s);
        }
        return max;
    }

    static boolean check(int N,int pos){return (N & (1<<pos)) != 0;}
    static int set(int N,int pos){return N=N | (1<<pos);}
    static int reset(int N,int pos){return N= N & ~(1<<pos);}

    static int reverse[];
    static void preCal(int d, int n) {
        int l = (1 << d);
        segTrees = new SegTree[l];
        reverse = new int[l];
        for (int j = 0; j < l; j++) {
            segTrees[j] = new SegTree(n+1);
            int x = 0;
            for(int k = 0; k < d; k++) {
                if (check(j, k)) x = reset(x, k);
                else x = set(x, k);
            }
            reverse[j] = x;
        }
    }

    static class SegTree {
        int t[];
        int n;
        SegTree(int N ){
            t = new int[2*N];
            n = t.length;
        }
        void clear() {
            Arrays.fill(t, 0);
        }
        public int get(int i) {
            return t[i + n / 2];
        }
        public void update(int i, int value) {
            i += n / 2;
            t[i] = value;
            for (; i > 1; i >>= 1)
                t[i >> 1] = Math.max(t[i], t[i ^ 1]);
        }
        public int query(int a, int b) { // max[a, b]
            int res = Integer.MIN_VALUE;
            for (a += n / 2, b += n / 2; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
                if ((a & 1) != 0)
                    res = Math.max(res, t[a]);
                if ((b & 1) == 0)
                    res = Math.max(res, t[b]);
            }
            return res;
        }
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;

        public FastReader(InputStream is) {
            this.is = is;
        }

        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }



        public String nextLine() {
            int c = skip();
            StringBuilder sb = new StringBuilder();
            while (!isEndOfLine(c)){
                sb.appendCodePoint(c);
                c = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        public char readChar() {
            return (char) skip();
        }
    }
}