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.math.BigInteger;
import java.security.SecureRandom;
import java.text.DecimalFormat;
import java.util.*;
import java.io.*;




public class Main {
    private static int MAXN = 200*1000;
    private static final int MAXST = 1 << 19;
    private static int [] [] P,f;
    private static int n,k,dims;
    private static int [] [] ST;
    private static int sgn(int x) {
        x = Math.min(x,1);
        return 2*x - 1;
    }
    private static int argmax(int a,int b,int i) {
        if (f[a][i] >= f[b][i]) return a;
        return b;
    }
    private static void build(int cur,int s,int e){
        if (s == e) {
            for (int i = 0;i < dims;i++)
                ST[cur][i] = s;
            return;
        }
        int m = (s + e) >> 1,left = 2*cur + 1,right = left + 1;
        build(left,s,m);
        build(right,m+1,e);
        for (int i = 0;i < dims;i++)
            ST[cur][i] = argmax(ST[left][i],ST[right][i],i);
    }
    private static int [] query(int cur,int s,int e,int l,int r) {
        if (l <= s && e <= r) return ST[cur].clone();
        int m = (s + e) >> 1,left = 2*cur + 1,right = left + 1;
        if (r <= m) return query(left,s,m,l,r);
        if (m < l) return query(right,m+1,e,l,r);
        int [] A = query(left,s,m,l,m);
        int [] B = query(right,m+1,e,m+1,r);
        for (int i = 0;i < dims;i++)
            A[i] = argmax(A[i],B[i],i);
        return A;
    }
    private static void update(int cur,int s,int e,int p) {
        if (s == e) return;
        int m = (s + e) >> 1,left = 2*cur + 1,right = left + 1;
        if (p <= m) update(left,s,m,p);
        else update(right,m+1,e,p);
        for (int i = 0;i < dims;i++)
            ST[cur][i] = argmax(ST[left][i],ST[right][i],i);
    }
    private static int dist(int a,int b) {
        int ret = 0;
        for (int i = 0;i < k;i++){
            ret += Math.abs(P[a][i] - P[b][i]);
        }
        return ret;
    }
    public static void main(String[] args) throws Exception {
        IO io ;
        try {
            io = new IO("in.in", null);
        } catch (IOException e) {
            io = new IO(null, null);
        }
        n = io.getNextInt();
        k = io.getNextInt();
        dims = 1 << k;
        P = new int[n][k];
        f = new int[n][dims];
        ST = new int[MAXST][dims];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < k;j++)
                P[i][j] = io.getNextInt();
            for (int msk = 0;msk < dims;msk++) {
                for (int j = 0;j < k;j++)
                    f[i][msk] += P[i][j]*sgn((msk >> j)&1);
            }
        }
        build(0,0,n-1);
        int m = io.getNextInt();
        for (;m > 0;m--) {
            int type = io.getNextInt();
            if (type == 1) {
                int i = io.getNextInt() - 1;
                for (int j = 0;j < k;j++)
                    P[i][j] = io.getNextInt();
                for (int msk = 0;msk < dims;msk++) {
                    f[i][msk] = 0;
                    for (int j = 0;j < k;j++)
                        f[i][msk] += P[i][j]*sgn((msk >> j)&1);
                }
                update(0,0,n-1,i);
            }
            else {
                int l = io.getNextInt()-1,r = io.getNextInt()-1;
                int [] Q = query(0,0,n-1,l,r);
//                System.err.println("==========================");
//                for (int [] p : P)
//                    System.err.println(Arrays.toString(p));
//                System.err.println("**************************");
//                for (int p : Q)
//                    System.err.println(Arrays.toString(P[p]));
                int ans = 0;
                for (int i = 0;i < dims;i++){
                    int j = (dims-1)^i;
                    ans = Math.max(ans,dist(Q[i],Q[j]));
                }
                io.println(ans);
            }
        }

        io.close();
    }
    private static final int onebillion7 = 1000000007;
}


class MCMF{
    public static long oo = 1L << 60,inf = oo/300;
    private int n,src,snk;
    public ArrayList<Integer> fr,to;
    public ArrayList<Integer> cap;
    private ArrayList<Long> cost;
    private ArrayList<Boolean> isInner;
    private long [] dist;
    private int [] iE;

    public MCMF(int n,int src,int snk) {
        this.n = n;
        this.src = src;
        this.snk = snk;
        dist = new long[n];
        iE = new int[n];
        fr = new ArrayList<>();
        to = new ArrayList<>();
        cap = new ArrayList<>();
        cost = new ArrayList<>();
        isInner = new ArrayList<>();
    }

    private int addEdge(int a,int b,int w,long c,boolean inner) {
        int e = fr.size();
        fr.add(a);
        to.add(b);
        cap.add(w);
        cost.add(c);
        isInner.add(inner);
        return e;
    }
    public int addEdge(int a,int b,int w1,int w2,long c,boolean inner) {
        int e = addEdge(a,b,w1,c,inner);
        addEdge(b,a,w2,-c,inner);
        return e;
    }



    private static boolean [] vis;
    private boolean exists(){
        if (vis == null) vis = new boolean[n];
        for (int i = 0;i < vis.length;i++) vis[i] = false;
        if (dist[snk] >= oo) return false;
        int u = snk;
        while (u != src) {
            if (vis[u]) return false;
            vis[u] = true;
            if (iE[u] == -1) return false;
            u = fr.get(iE[u]);
        }
        return true;
    }
    private boolean bellman(){
        for (int i = 0;i < n;i++) {
            dist[i] = oo;
            iE[i] = -1;
        }
        dist[src] = 0;
        for (int i = 0;i < n-1;i++)
            for (int e = 0;e < fr.size();e++) {
                int a = fr.get(e),b = to.get(e);
                int ca = cap.get(e);
                long co = cost.get(e);
                if (ca == 0) continue;
                if (dist[a] + co < dist[b]) {
                    dist[b] = dist[a] + co;
                    iE[b] = e;
                }
            }
        return exists();
    }

    private pair augment(){
        ArrayList<Integer> path = new ArrayList<>();
        int u = snk;
        int f = Integer.MAX_VALUE;
        long c = 0;
        while (u != src) {
            path.add(u);
            int e = iE[u];
            f = Math.min(f,cap.get(e));
            if (!isInner.get(e))
                c += cost.get(e);
            u = fr.get(e);
        }
        path.add(src);
        Collections.reverse(path);

        u = snk;
        int ctr = 0;
        while (u != src) {
            int e = iE[u];
            ctr += isInner.get(e) ? 1 : 0;
            cap.set(e,cap.get(e) - f);
            cap.set(e^1,cap.get(e^1) + f);
            u = fr.get(e);
        }
        return new pair(f,c*f);
    }

    public pair mcmf(){
        long cost = 0;
        int flow = 0;
        while (bellman())  {
            pair res = augment();
            cost += res.cost;
            flow += res.flow;
        }
        return new pair(flow,cost);
    }
}

class pair{
    int flow;
    long cost;
    public pair(int f,long c) {
        flow = f;
        cost = c;
    }
}

class Buffer{
    ArrayList<Character> AS;
    public Buffer(){
        AS = new ArrayList<>();
    }
    public void append(String s){
        for (char c : s.toCharArray())
            AS.add(c);
    }
    public void appendLine(String s) {
        append(s);
        AS.add('\n');
    }
    public void clear(){
        AS.clear();
    }
    public String toString(){
        StringBuilder sb = new StringBuilder();
        for (char c : AS)
            sb.append(c);
        return sb.toString();
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}



class PollardRho {
    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE  = new BigInteger("1");
    private final static BigInteger TWO  = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();
    private static ArrayList<Long> primes = new ArrayList<>();

    private static BigInteger rho(BigInteger N) {
        BigInteger divisor;
        BigInteger c  = new BigInteger(N.bitLength(), random);
        BigInteger x  = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        // check divisibility by 2
        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

        do {
            x  =  x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    private static void factor(BigInteger N) {
        if (N.compareTo(ONE) == 0) return;
        if (N.isProbablePrime(20)) {
            primes.add(N.longValue());
            return;
        }
        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }


    public static ArrayList<Long> factor(Long n) {
        primes.clear();
        factor(BigInteger.valueOf(n));
        return primes;
    }
}
