static class FenwickTree {

            int size;
            long[] tree;

            FenwickTree(int n) {
                size = n + 1;
                tree = new long[size + 1];
            }

            void inc(int left, int right, long delta) {
                update(left, delta);
                update(right + 1, -delta);
            }

            void update(int index, long delta) {
                for (; index < size; index |= (index + 1)) {
                    tree[index] += delta;
                }
            }

            long get(int v) {
                long sum = 0;
                for (; v >= 0; v &= (v + 1), --v) {
                    sum += tree[v];
                }
                return sum;
            }
        }

        static class MainPathProcessor extends AbstractQueryProcessor {

            int[] mainPathIndexes;
            long[] mainPathDistances;
            FenwickTree tree;

            @Override
            void additionalInit() {
                dijkstraInit();

                mainPathInit();
                initUpdates();
            }

            void mainPathInit() {
                this.mainPathIndexes = new int[size];
                Arrays.fill(mainPathIndexes, -1);

                this.mainPathDistances = new long[size];
                Arrays.fill(mainPathDistances, INF);

                int start = vertices[0][0], end = vertices[m - 1][n - 1];
                dijkstra(start, end, START_MODE, size + 1);

                List<Integer> path = new ArrayList<Integer>();
                for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
                    path.add(cur);
                }

                Collections.reverse(path);
                for (int index = 0; index < path.size(); ++index) {
                    int v = path.get(index);
                    mainPathIndexes[v] = index;
                    mainPathDistances[v] = modeDistances[START_MODE][v];
                }

                this.tree = new FenwickTree(path.size());
            }

            final int START_MODE = 0, END_MODE = 1;

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

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

            Queue<Vertex>[] modeQueues;

            final long INF = Long.MAX_VALUE / 2 - 1000L * 1000 * 1000 * 1000 * 1000;

            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 dijkstraInit() {
                this.modeDistances = new long[2][size];
                this.modeParents = new int[2][size];
                this.modeSteps = 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);
                }
            }

            List<Integer> dijkstra(int start, int end, int mode, int maxSteps) {
                ++curColor;
                colorsSeen[start] = curColor;

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

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

                int[] steps = modeSteps[mode];
                steps[start] = 0;

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

                List<Integer> neighbors = new ArrayList<Integer>();
                while (queue.size() > 0) {

                    Vertex v = queue.poll();
                    if (colorsProcessed[v.index] == curColor) continue;

                    int from = v.index;
                    neighbors.add(from);

                    if (steps[from] == maxSteps) continue;

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

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

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

                    colorsProcessed[from] = curColor;
                }

                return neighbors;
            }

            int[] updateColors;
            int updateCurColor;

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

            final int UPDATE_DIJKSTRA_MAX_STEPS = 50;

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

                List<Integer> startNeighbors = dijkstra(start, end, START_MODE, UPDATE_DIJKSTRA_MAX_STEPS);
                List<Integer> endNeighbors = dijkstra(end, start, END_MODE, UPDATE_DIJKSTRA_MAX_STEPS);

                int optimalStartEnd = -1, optimalEndEnd = -1;
                long optimalDistance = INF;

                for (int startEnd : startNeighbors) {
                    long startDistance = modeDistances[START_MODE][startEnd];
                    int startPathIndex = mainPathIndexes[startEnd];

                    for (int endEnd : endNeighbors) {
                        long endDistance = modeDistances[END_MODE][endEnd];
                        int endPathIndex = mainPathIndexes[endEnd];

                        if (startEnd == endEnd) {
                            if (optimalDistance > startDistance + endDistance) {
                                optimalDistance = startDistance + endDistance;
                                optimalStartEnd = startEnd;
                                optimalEndEnd = endEnd;
                            }
                        } else {
                            if (startPathIndex != -1 && endPathIndex != -1) {
                                long totalDistance = startDistance + Math.abs(mainPathDistances[startEnd] - mainPathDistances[endEnd]) + endDistance;
                                if (optimalDistance > totalDistance) {
                                    optimalDistance = totalDistance;
                                    optimalStartEnd = startEnd;
                                    optimalEndEnd = endEnd;
                                }
                            }
                        }
                    }
                }

                if (optimalDistance == INF) {
                    throw new UnsupportedOperationException();
                }

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

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

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

                    int startPathIndex = mainPathIndexes[optimalStartEnd];
                    int endPathIndex = mainPathIndexes[optimalEndEnd];

                    if (startPathIndex > endPathIndex) {
                        int tmp = startPathIndex;
                        startPathIndex = endPathIndex;
                        endPathIndex = tmp;
                    }

                    tree.inc(startPathIndex, endPathIndex, delta);
                }
            }

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

                int mainPathIndex = mainPathIndexes[v];
                if (mainPathIndex != -1) {
                    value = tree.get(mainPathIndex);
                }

                return value;
            }
        }

        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;
        }