static class BlockProcessor extends AbstractQueryProcessor {

            static final int BLOCK_SIZE = 250;

            int blockSize;

            int blocksCount;
            int[] blocks;

            int blockSideSize;
            int[][] blockSideVertices;
            int[] blockInnerIndexes;

            boolean[][] blockSideActive;

            boolean[][][] blockSidesPathContains;
            long[][][] blockSidesPathDeltas;

            long[][][] blockSidesPathLengths;
            boolean[][][] blockSidesPathInner;

            int[] blockGlobalVertices;
            int[] blockGlobalIndexes;

            int blockGlobalGraphSize;
            Edge[][] blockGlobalGraph;

            long[][] blockGlobalPathLengths;

            public BlockProcessor() {
                this(BLOCK_SIZE);
            }

            public BlockProcessor(int blockSize) {
                this.blockSize = blockSize;
            }

            @Override
            void additionalInit() {
                this.blockSize = min(blockSize, n);

                this.blocks = generateBlocks(m, n, size, vertices, blockSize);
                this.blocksCount = calculateBlocksCount(blocks);

                this.blockSideSize = 2 * m;

                this.blockSideVertices = generateBlockSideVertices(m, n, vertices, blocks, blocksCount, blockSideSize);
                this.blockInnerIndexes = generateBlockInnerIndexes(size, blockSideVertices);

                prepareBlockSidesPaths();
                prepareBlockGlobalGraph();
                prepareBlockGlobalPaths();

                initUpdates();
            }

            void prepareBlockGlobalPaths() {
                this.blockGlobalPathLengths = new long[blockGlobalGraphSize][blockGlobalGraphSize];

                final long[] distances = new long[blockGlobalGraphSize];

                Queue<Vertex> queue = new PriorityQueue<Vertex>(blockGlobalGraphSize * (blockSideSize + 1));

                int[] blockGlobalColorsSeen = new int[blockGlobalGraphSize];
                int[] blockGlobalColorsProcessed = new int[blockGlobalGraphSize];
                int blockGlobalColor = 1;

                for (int start = 0; start < blockGlobalGraphSize; ++start) {
                    ++blockGlobalColor;
                    blockGlobalColorsSeen[start] = blockGlobalColor;

                    distances[start] = 0;
                    queue.add(new Vertex(start, distances[start]));

                    while (queue.size() > 0) {
                        Vertex v = queue.poll();
                        int from = v.index;
                        if (blockGlobalColorsProcessed[from] == blockGlobalColor) continue;

                        long fromDistance = distances[from];
                        for (Edge e : blockGlobalGraph[from]) {
                            int to = e.to;

                            if (blockGlobalColorsSeen[to] != blockGlobalColor) {
                                distances[to] = INF;
                                blockGlobalColorsSeen[to] = blockGlobalColor;
                            }

                            if (distances[to] > fromDistance + e.w) {
                                distances[to] = fromDistance + e.w;
                                queue.add(new Vertex(to, distances[to]));
                            }
                        }

                        blockGlobalColorsProcessed[from] = blockGlobalColor;
                    }

                    for (int end = 0; end < blockGlobalGraphSize; ++end) {
                        blockGlobalPathLengths[start][end] = distances[end];
                    }
                }
            }

            void prepareBlockGlobalGraph() {
                this.blockGlobalVertices = generateBlockGlobalVertices(blocksCount, blockSideSize, blockInnerIndexes);
                this.blockGlobalGraphSize = blockGlobalVertices.length;

                this.blockGlobalIndexes = generateBlockGlobalIndexes(size, blockGlobalVertices);

                List<Edge>[] blockGlobalEdgeLists = new List[blockGlobalGraphSize];
                for (int v = 0; v < blockGlobalGraphSize; ++v) {
                    blockGlobalEdgeLists[v] = new ArrayList<Edge>();
                }

                for (int i = 0; i < m; ++i) {
                    for (int j = 1; j < n - 1; ++j) {
                        int cur = vertices[i][j];
                        int next = vertices[i][j + 1];

                        int curBlock = blocks[cur], nextBlock = blocks[next];
                        if (curBlock != nextBlock) {
                            int curGlobalVertex = blockGlobalIndexes[cur], nextGlobalVertex = blockGlobalIndexes[next];

                            long weight = right[i][j];

                            blockGlobalEdgeLists[curGlobalVertex].add(new Edge(nextGlobalVertex, weight));
                            blockGlobalEdgeLists[nextGlobalVertex].add(new Edge(curGlobalVertex, weight));
                        }
                    }
                }

                for (int block = 0; block < blocksCount; ++block) {
                    for (int i = 0; i < blockSideSize; ++i) {
                        if (!blockSideActive[block][i]) continue;

                        int from = blockSideVertices[block][i];
                        int fromGlobalVertex = blockGlobalIndexes[from];

                        for (int j = 0; j < blockSideSize; ++j) {
                            if (!blockSideActive[block][j]) continue;

                            int to = blockSideVertices[block][j];
                            if (from == to) continue;

                            int toGlobalVertex = blockGlobalIndexes[to];
                            long weight = blockSidesPathLengths[block][i][j];

                            blockGlobalEdgeLists[fromGlobalVertex].add(new Edge(toGlobalVertex, weight));
                        }
                    }
                }

                this.blockGlobalGraph = new Edge[blockGlobalGraphSize][];
                for (int v = 0; v < blockGlobalGraphSize; ++v) {
                    blockGlobalGraph[v] = blockGlobalEdgeLists[v].toArray(new Edge[0]);
                }
            }

            void prepareBlockSidesPaths() {
                this.blockSideActive = new boolean[blocksCount][blockSideSize];
                for (int v = 0; v < size; ++v) {
                    int block = blocks[v];
                    int sideIndex = blockInnerIndexes[v];
                    if (sideIndex != -1) {
                        blockSideActive[block][sideIndex] = true;
                    }
                }

                this.blockSidesPathDeltas = new long[blocksCount][blockSideSize][blockSideSize];

                this.blockSidesPathContains = new boolean[blockSideSize][blockSideSize][size];
                this.blockSidesPathLengths = new long[blocksCount][blockSideSize][blockSideSize];
                this.blockSidesPathInner = new boolean[blocksCount][blockSideSize][blockSideSize];

                blockInnerDijkstraInit();

                for (int block = 0; block < blocksCount; ++block) {
                    int[] blockSide = blockSideVertices[block];

                    for (int start : blockSide) {
                        int blockInnerIndexStart = blockInnerIndexes[start];

                        blockInnerDijkstra(start, START_MODE);

                        for (int end : blockSide) {
                            int blockInnerIndexEnd = blockInnerIndexes[end];

                            blockSidesPathInner[block][blockInnerIndexStart][blockInnerIndexEnd] = (start != end);

                            for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {

                                if (blockInnerIndexes[cur] != -1) {
                                    if (cur != end && cur != start) {
                                        blockSidesPathInner[block][blockInnerIndexStart][blockInnerIndexEnd] = false;
                                        break;
                                    }
                                }
                            }

                            blockSidesPathDeltas[block][blockInnerIndexStart][blockInnerIndexEnd] = 0;

                            if (blockSidesPathInner[block][blockInnerIndexStart][blockInnerIndexEnd]) {
                                blockSidesPathLengths[block][blockInnerIndexStart][blockInnerIndexEnd] = modeDistances[START_MODE][end];

                                for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
                                    if (blockInnerIndexes[cur] != -1) continue;

                                    // we only need really inner vertices
                                    blockSidesPathContains[blockInnerIndexStart][blockInnerIndexEnd][cur] = true;
                                }
                            } else {
                                blockSidesPathLengths[block][blockInnerIndexStart][blockInnerIndexEnd] = INF;
                            }
                        }
                    }
                }
            }

            final int START_MODE = 0, END_MODE = 1;

            long[][] modeDistances;
            int[][] modeParents;

            int[] colorsSeen;
            int[] colorsProcessed;
            int curColor;

            Queue<Vertex>[] modeQueues;

            final long INF = Long.MAX_VALUE / 2;

            class Vertex implements Comparable<Vertex> {
                int index;
                long distance;
                public Vertex(int index, long distance) {
                    super();
                    this.index = index;
                    this.distance = distance;
                }
                @Override
                public int compareTo(Vertex other) {
                    long iDistance = distance, jDistance = other.distance;
                    return (iDistance < jDistance) ? -1 : ((iDistance > jDistance) ? 1 : 0);
                }
            }

            void blockInnerDijkstraInit() {
                this.modeDistances = new long[2][size];
                this.modeParents = new int[2][size];

                this.colorsSeen = new int[size];
                this.colorsProcessed = new int[size];
                this.curColor = 1;

                this.modeQueues = new Queue[2];
                for (int i = 0; i < 2; ++i) {
                    final int mode = i;
                    modeQueues[mode] = new PriorityQueue<Vertex>(size);
                }
            }

            void blockInnerDijkstra(int start, int mode) {
                int block = blocks[start];

                ++curColor;
                colorsSeen[start] = curColor;

                long[] distances = modeDistances[mode];
                distances[start] = 0;

                int[] parents = modeParents[mode];
                parents[start] = -1;

                Queue<Vertex> queue = modeQueues[mode];
                queue.add(new Vertex(start, 0));

                while (queue.size() > 0) {
                    Vertex v = queue.poll();
                    if (colorsProcessed[v.index] == curColor) continue;

                    int from = v.index;
                    long fromDistance = distances[from];
                    for (Edge e : graph[from]) {
                        int to = e.to;
                        if (blocks[to] != block) continue;

                        if (colorsSeen[to] != curColor) {
                            distances[to] = INF;
                            parents[to] = -1;
                            colorsSeen[to] = curColor;
                        }

                        if (distances[to] > fromDistance + e.w) {
                            distances[to] = fromDistance + e.w;
                            parents[to] = from;
                            queue.add(new Vertex(to, distances[to]));
                        }
                    }

                    colorsProcessed[from] = curColor;
                }
            }

            int[] updateColors;
            int updateCurColor;

            void initUpdates() {
                this.updateColors = new int[size];
                this.updateCurColor = 1;
            }

            @Override
            void updatePath(int start, int end, long delta) {
                ++updateCurColor;

                blockInnerDijkstra(start, START_MODE);
                blockInnerDijkstra(end, END_MODE);

                int startBlock = blocks[start], endBlock = blocks[end];

                long startEndLength = INF;
                int startOptimalSide = -1, endOptimalSide = -1;
                if (startBlock == endBlock) {
                    startEndLength = modeDistances[START_MODE][end];
                }

                for (int startSide = 0; startSide < blockSideSize; ++startSide) {
                    if (!blockSideActive[startBlock][startSide]) continue;

                    int startSideVertex = blockSideVertices[startBlock][startSide];
                    long startSideDistance = modeDistances[START_MODE][startSideVertex];

                    int startSideGlobalVertex = blockGlobalIndexes[startSideVertex];

                    for (int endSide = 0; endSide < blockSideSize; ++endSide) {
                        if (!blockSideActive[endBlock][endSide]) continue;

                        int endSideVertex = blockSideVertices[endBlock][endSide];
                        long endSideDistance = modeDistances[END_MODE][endSideVertex];

                        int endSideGlobalVertex = blockGlobalIndexes[endSideVertex];

                        long startEndSideDistance = startSideDistance + blockGlobalPathLengths[startSideGlobalVertex][endSideGlobalVertex] + endSideDistance;
                        if (startEndSideDistance < startEndLength) {
                            startEndLength = startEndSideDistance;
                            startOptimalSide = startSide;
                            endOptimalSide = endSide;
                        }
                    }
                }

                if (startOptimalSide == -1 || endOptimalSide == -1) {
                    // inner path
                    for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
                        vertexValues[cur] += delta;
                    }
                } else {
                    int startOptimalVertex = blockSideVertices[startBlock][startOptimalSide];
                    int startOptimalGlobalVertex = blockGlobalIndexes[startOptimalVertex];

                    int endOptimalVertex = blockSideVertices[endBlock][endOptimalSide];
                    int endOptimalGlobalVertex = blockGlobalIndexes[endOptimalVertex];

                    for (int cur = startOptimalVertex; cur != -1; cur = modeParents[START_MODE][cur]) {
                        if (updateColors[cur] == updateCurColor) continue;
                        vertexValues[cur] += delta;
                        updateColors[cur] = updateCurColor;
                    }

                    for (int cur = endOptimalVertex; cur != -1; cur = modeParents[END_MODE][cur]) {
                        if (updateColors[cur] == updateCurColor) continue;
                        vertexValues[cur] += delta;
                        updateColors[cur] = updateCurColor;
                    }

                    long startEndGlobalDistance = blockGlobalPathLengths[startOptimalGlobalVertex][endOptimalGlobalVertex];

                    for (int block = 0; block < blocksCount; ++block) {
                        for (int startSide = 0; startSide < blockSideSize; ++startSide) {
                            if (!blockSideActive[block][startSide]) continue;

                            int startVertex = blockSideVertices[block][startSide];
                            int startGlobalVertex = blockGlobalIndexes[startVertex];

                            long startGlobalDistance = blockGlobalPathLengths[startOptimalGlobalVertex][startGlobalVertex];

                            for (int endSide = 0; endSide < blockSideSize; ++endSide) {
                                if (!blockSideActive[block][endSide]) continue;

                                if (!blockSidesPathInner[block][startSide][endSide]) continue;

                                int endVertex = blockSideVertices[block][endSide];
                                int endGlobalVertex = blockGlobalIndexes[endVertex];

                                long endGlobalDistance = blockGlobalPathLengths[endGlobalVertex][endOptimalGlobalVertex];

                                long startEndInnerDistance = blockSidesPathLengths[block][startSide][endSide];///[startGlobalVertex][endGlobalVertex];
                                if (startGlobalDistance + startEndInnerDistance + endGlobalDistance == startEndGlobalDistance) {
                                    blockSidesPathDeltas[block][startSide][endSide] += delta;

                                    if (updateColors[startVertex] != updateCurColor) {
                                        updateColors[startVertex] = updateCurColor;
                                        vertexValues[startVertex] += delta;
                                    }

                                    if (updateColors[endVertex] != updateCurColor) {
                                        updateColors[endVertex] = updateCurColor;
                                        vertexValues[endVertex] += delta;
                                    }
                                }
                            }
                        }
                    }


                }
            }

            @Override
            long getVertexValue(int v) {
                long value = 0;

                int block = blocks[v];
                for (int start = 0; start < blockSideSize; ++start) {
                    for (int end = 0; end < blockSideSize; ++end) {
                        if (blockSidesPathInner[block][start][end] && blockSidesPathContains[start][end][v]) {
                            value += blockSidesPathDeltas[block][start][end];
                        }
                    }
                }

                return value;
            }
        }

        static int[] generateBlockGlobalIndexes(int size, int[] blockGlobalVertices) {
            int[] blockGlobalIndexes = new int[size];
            Arrays.fill(blockGlobalIndexes, -1);

            for (int index = 0; index < blockGlobalVertices.length; ++index) {
                blockGlobalIndexes[blockGlobalVertices[index]] = index;
            }

            return blockGlobalIndexes;
        }
        static int[] generateBlockGlobalVertices(int blocksCount, int blockSideSize, int[] blockInnerIndexes) {
            List<Integer> blockGlobalVertices = new ArrayList<Integer>();

            for (int v = 0; v < blockInnerIndexes.length; ++v) {
                if (blockInnerIndexes[v] != -1) {
                    blockGlobalVertices.add(v);
                }
            }

            return castInt(blockGlobalVertices);
        }
        static int[] generateBlockInnerIndexes(int size, int[][] blockSideVertices) {
            int[] blockInnerIndexes = new int[size];
            Arrays.fill(blockInnerIndexes, -1);

            for (int[] blockSide : blockSideVertices) {
                for (int index = 0; index < blockSide.length; ++index) {
                    blockInnerIndexes[blockSide[index]] = index;
                }
            }

            return blockInnerIndexes;
        }

        static int[][] generateBlockSideVertices(int m, int n, int[][] vertices, int[] blocks, int blocksCount, int blockSideSize) {
            int[][] blockSideVertices = new int[blocksCount][blockSideSize];
            int[] blockSizes = new int[blocksCount];

            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int cur = vertices[i][j];
                    int curBlock = blocks[cur];

                    if (j == 0 || j == n - 1) {
                        blockSideVertices[curBlock][blockSizes[curBlock]++] = cur;

                        // it is more comfortable to have block sides of length 6 every time, even when n == 1
                        if (n - 1 == 0) {
                            blockSideVertices[curBlock][blockSizes[curBlock]++] = cur;
                        }
                    } else {
                        int next = vertices[i][j + 1];

                        int nextBlock = blocks[next];
                        if (curBlock != nextBlock) {
                            blockSideVertices[curBlock][blockSizes[curBlock]++] = cur;
                            blockSideVertices[nextBlock][blockSizes[nextBlock]++] = next;
                        }
                    }
                }
            }

            return blockSideVertices;
        }

        static int[] generateBlocks(int m, int n, int size, int[][] vertices, int blockSize) {
            int[] blocks = new int[size];

            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int v = vertices[i][j];
                    blocks[v] = j / blockSize;
                }
            }

            return blocks;
        }

        static int calculateBlocksCount(int[] blocks) {
            return getMinMax(blocks).y + 1;
        }

        interface QueryProcessor {

            QueryProcessor init(int m, int n, long[][] down, long[][] right);

            void update(int i1, int j1, int i2, int j2, long delta);
            long get(int i, int j);
        }

        static abstract class AbstractQueryProcessor implements QueryProcessor {

            int m, n;
            long[][] down;
            long[][] right;

            int size;
            int[][] vertices;

            Edge[][] graph;

            long[] vertexValues;

            @Override
            public QueryProcessor init(int m, int n, long[][] down, long[][] right) {
                this.m = m;
                this.n = n;

                this.down = down;
                this.right = right;

                this.size = m * n;
                this.vertices = generateIndexes(m, n);
                this.graph = generateMatrixGraph(m, n, size, vertices, down, right);

                this.vertexValues = new long[size];

                additionalInit();

                return this;
            }

            abstract void additionalInit();

            @Override
            public void update(int i1, int j1, int i2, int j2, long delta) {
                updatePath(vertices[i1][j1], vertices[i2][j2], delta);
            }

            abstract void updatePath(int from, int to, long delta);

            @Override
            public long get(int i, int j) {
                int v = vertices[i][j];
                return vertexValues[v] + getVertexValue(v);
            }

            abstract long getVertexValue(int v);
        }


        static int[][] generateIndexes(int m, int n) {
            int[][] indexes = new int[m][n];
            for (int i = 0, index = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j, ++index) {
                    indexes[i][j] = index;
                }
            }

            return indexes;
        }


        static Edge[][] generateMatrixGraph(int m, int n, int size, int[][] vertices, long[][] down, long[][] right) {
            List<Edge>[] edgeLists = new List[size];
            for (int v = 0; v < size; ++v) {
                edgeLists[v] = new ArrayList<Edge>();
            }

            for (int i = 0; i < m - 1; ++i) {
                for (int j = 0; j < n; ++j) {
                    int from = vertices[i][j];
                    int to = vertices[i + 1][j];

                    long weight = down[i][j];

                    edgeLists[from].add(new Edge(to, weight));
                    edgeLists[to].add(new Edge(from, weight));
                }
            }

            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n - 1; ++j) {
                    int from = vertices[i][j];
                    int to = vertices[i][j + 1];

                    long weight = right[i][j];

                    edgeLists[from].add(new Edge(to, weight));
                    edgeLists[to].add(new Edge(from, weight));
                }
            }

            Edge[][] graph = new Edge[size][];
            for (int v = 0; v < size; ++v) {
                graph[v] = edgeLists[v].toArray(new Edge[0]);
            }

            return graph;
        }