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.util.*;
import java.io.*;
import static java.lang.Math.*;
public class Main {
    static final long MOD = 1_000_000_007, INF = 1_000_000_000_000_000_000L;
    static final int INf = 1_000_000_000;
    static FastReader reader;
    static PrintWriter writer;
    public static void main(String[] args) {
        Thread t = new Thread(null, new O(), "Integer.MAX_VALUE", 100000000);
        t.start();
    }
    static class O implements Runnable {
        public void run() {
            try {
                magic();
            }
            catch (Exception e) {
                e.printStackTrace();
                System.exit(1);
            }
        }
    }
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64];
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }
    //variables here
    static int n,k;
    static long arr[][], maxtree[][],mintree[][],temp[],mintemp[], maxtemp[];
    static void magic() throws IOException{
        reader = new FastReader();
        writer = new PrintWriter(System.out, true);
        n = reader.nextInt();
        k = reader.nextInt();
        arr = new long[(1<<k)][n];
        int sz = (int)(pow(2, ceil(log(n)/log(2))+1));
        maxtree = new long[(1<<k)][sz];
        mintree = new long[(1<<k)][sz];
        temp = new long[k];
        for(int i=0;i<n;++i) {
            for(int j=0;j<k;++j) {
                temp[j] = reader.nextLong();
            }
            for(int mask=0;mask<(1<<k);++mask) {
                long val = 0;
                for(int j=0;j<k;++j) {
                    if((mask&(1<<j))!=0) {
                        val-=temp[j];
                    }
                    else {
                        val+=temp[j];
                    }
                }
                arr[mask][i] = val;
            }
        }
        mintemp = new long[(1<<k)];
        maxtemp = new long[(1<<k)];
        build(1,0,n-1);
        int q = reader.nextInt();
        while(q-->0) {
            if(reader.nextInt()==1) {
                 int idx = reader.nextInt()-1;
                 for(int i=0;i<k;++i) {
                     temp[i] = reader.nextLong();
                 }
                for(int mask=0;mask<(1<<k);++mask) {
                    long val = 0;
                    for(int j=0;j<k;++j) {
                        if((mask&(1<<j))!=0) {
                            val-=temp[j];
                        }
                        else {
                            val+=temp[j];
                        }
                    }
                    arr[mask][idx] = val;
                }
                update(1,0,n-1,idx);
            }
            else {
                int l = reader.nextInt()-1, r = reader.nextInt()-1;
                long ans = Long.MIN_VALUE;
                for(int i=0;i<(1<<k);++i) {
                    maxtemp[i] = Long.MIN_VALUE;
                    mintemp[i] = Long.MAX_VALUE;
                }
                query(1,0,n-1,l,r);
                for(int i=0;i<(1<<k);++i) {
                    ans = max(ans, maxtemp[i]-mintemp[i]);
                }
                writer.println(ans);
            }
        }
    }
    static void build(int treein,int low,int high)
    {
        if(low==high) {
            for(int i=0;i<(1<<k);++i) {
                maxtree[i][treein] = mintree[i][treein] = arr[i][low];
            }
        }
        else
        {
            int mid = (low+high)>>1;
            build(2*treein,low,mid);
            build(2*treein+1,mid+1,high);
            for(int treeidx=0;treeidx<(1<<k);++treeidx) {
                maxtree[treeidx][treein] = max(maxtree[treeidx][2*treein], maxtree[treeidx][2*treein+1]);
                mintree[treeidx][treein] = min(mintree[treeidx][2*treein], mintree[treeidx][2*treein+1]);
            }
        }
    }
    static void update(int treein,int low,int high,int idx)
    {
        if(low==high) {
            for(int i=0;i<(1<<k);++i) {
                maxtree[i][treein] = mintree[i][treein] = arr[i][low];
            }
        }
        else
        {
            int mid = (low+high)>>1;
            if(idx<=mid)
                update(2*treein,low,mid,idx);
            else update(2*treein+1,mid+1,high,idx);
            for(int treeidx=0;treeidx<(1<<k);++treeidx) {
                maxtree[treeidx][treein] = max(maxtree[treeidx][2*treein], maxtree[treeidx][2*treein+1]);
                mintree[treeidx][treein] = min(mintree[treeidx][2*treein], mintree[treeidx][2*treein+1]);
            }
        }
    }
    static void query(int treein,int low,int high,int l,int r)
    {
        if(l<=low && high<=r) {
            for(int i=0;i<(1<<k);++i) {
                mintemp[i] = min(mintemp[i], mintree[i][treein]);
                maxtemp[i] = max(maxtemp[i], maxtree[i][treein]);
            }
            return;
        }
        if(low>r || high<l)
            return;
        int mid = (low+high)>>1;
        query(2*treein, low, mid, l,r);
        query(2*treein+1, mid+1,high,l,r);
    }
}