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.*;

public class Multidimensional {

    private static StringTokenizer ST;
    private static BufferedReader BR;
    private static PrintWriter PW;

    private static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    private static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    private static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    private static String next() throws IOException {
        while (ST == null || !ST.hasMoreTokens())
            ST = new StringTokenizer(BR.readLine());
        return ST.nextToken();
    }


    private static int[][] MAX;
    private static int R;

    private long query(int l,int r,int k) {
        long cnt = 0;
        for (int i = 0; i < 1 << k; i++) {
            cnt = Long.max(cnt, Q(MAX[i], l, r) + Q(MAX[i ^ R], l, r));
        }
        return cnt;
    }
    

    private void update(int[] G,int n, int k){
        int L = 1<< k;
        for(int i = 0 ; i < L; ++i){
            int sum = 0;
            for(int j = 0;j< k;j++){
                // i = 0001  ; j=[0,1,2,3]
                if((i & 1<<j) > 0)
                    sum += G[j];
                else
                    sum -= G[j];
            }
            U(MAX[i],n,sum);
        }
    }

    private void U(int[] tree, int num ,int v) {
        int L = num + tree.length / 2;
        tree[L] = v;
        for (int i = L; i > 1; i >>= 1) {
            tree[i >> 1] = Math.max(tree[i], tree[i ^ 1]);
        }
    }

    private int Q(int[] tree, int a, int b){
        int res = Integer.MIN_VALUE;
        int n = tree.length;
        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, tree[a]);
            if ((b & 1) == 0)
                res = Math.max(res, tree[b]);
        }
        return res;
    }

    private void run() throws IOException {
        BR = new BufferedReader(new InputStreamReader(System.in));
        PW = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        int n = nextInt();
        int k = nextInt();
        int L = 1<<k;
        R = L-1;

        MAX = new int[L][n*2];
        for(int i = 0; i< L;i++){
            Arrays.fill(MAX[i],Integer.MIN_VALUE);
        }

        int[] G = new int[k];
        for (int i = 0; i<n; i++) {
            for (int j = 0; j < k; j++) {
                G[j] = nextInt();
            }
            update(G, i, k);
        }

        int q = nextInt();
        for(int i = 0; i<q; i++) {
            int t = nextInt();
            if (t == 1) {
                int pos = nextInt();

                for (int j = 0; j < k; j++) {
                    G[j] = nextInt();
                }
                update(G, pos - 1, k);
            } else if (t == 2) {
                int l = nextInt() - 1;
                int r = nextInt() - 1;
                PW.println(query(l, r, k));
            }
        }

        PW.close();
    }

    public static void main(String[] args) throws IOException {
        new Multidimensional().run();
    }
}
