Querying on a Grid

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Chef is helping out at a volunteering center for teaching. A child comes to Chef with a problem that he is not able to solve and asks Chef for his help. The problem is the following:
Consider an M × N grid graph. The vertices in the grid graph are identified by its row and column number, i.e., for a vertex there are two numbers (i,j) associated with it, where 1 ≤ i ≤ M is its row, and 1 ≤ j ≤ N is its column. There are two types of edges in a grid graph(note that all edges are bidirectional) :
 When i < M, there is an edge of weight down(i, j) connecting (i, j) and (i+1, j);
 When j < N, there is an edge of weight right(i, j) connecting (i, j) and (i, j+1).
Initially, every vertex has a weight of zero.
Define the length of a path to be the sum of weights of all the edges in this path. The shortest path between (i1, j1) and (i2, j2) is the path with the minimum length. Of course, the weights associated with vertices doesn't influence shortest paths at all.
The task in the problem is to process the following 2 types of queries on this graph efficiently :
 i1 j1 i2 j2 c : add c to the weights of all vertices in the shortest path between (i1, j1) and (i2, j2).
 i j : return the weight of vertex (i, j).
Chef is confused with the problem but he wants to help the child. Can you help Chef with this problem?
Input
The first line contains three integers M, N, Q. M and N denotes the graph's size; Q denotes the number of queries.
Next M  1 lines, each line contains N numbers. The jth number in the ith line in this part(i.e., the (i + 1)th line in total) denotes down(i, j).
Next M lines, each line contains N  1 numbers. The jth number in the ith line in this part(i.e., the (i + M)th line in total) denotes right(i, j).
Next Q lines, each line contains 3 or 6 numbers, denoting a query.
Output
For each query of type 2, output the weight of required vertex.
Constraints
 1 ≤ M ≤ 3
 1 ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 10^{5}
 1 ≤ down(i,j), right(i,j) ≤ 10^{12}
 In type 1 query :
 1 ≤ i1, i2 ≤ M
 1 ≤ j1, j2 ≤ N
 1 ≤ c ≤ 10^{13}
 The shortest path between (i1, j1) and (i2, j2) is unique.
 In type 2 query :
 1 ≤ i ≤ M
 1 ≤ j ≤ N
Subtasks
 Subtask #1 (6 points): N, Q ≤ 10^{3}
 Subtask #2: (11 points): M = 1.
 Subtask #3: (30 points): M = 2.
 Subtask #4: (24 points):
 down(i,j) and right(i,j) are uniformly randomly generated from [1,3 × 10^{10}].
 Queries are also randomly generated.
 There is only one test file for this subtask.
 Subtask #5: (29 points):: Original Constraints
Example
Input: 3 3 11 1 1 5 2 10 6 1 4 1 13 6 5 1 2 2 3 3 1 1 2 2 1 3 2 2 1 1 2 1 2 2 1 3 2 2 1 2 2 2 2 2 3 2 3 1 2 3 2 2 3 3 Output: 0 2 2 1 3 0 1 1 1
Explanation
Example case 1. See picture below.
The shortest path between (2,2) and (3,3) is (2,2)>(2,1)>(3,1)>(3,2)>(3,3). We add 1 to these 5 vertices.
The shortest path between (2,2) and (1,3) is (2,2)>(1,2)>(1,3). We add 2 to these 3 vertices.
Note that the shortest path between (1,1) and (2,2) is not unique. However, the queried paths are (2,2)(3,3) and (2,2)(1,3), and the shortest paths of these pairs of points are unique, so this data is valid.
Author:  r_64 
Tester:  jingbo_adm 
Editorial  https://discuss.codechef.com/problems/QGRID 
Tags  divideandconq, hard, r_64, sept17, shortestpath 
Date Added:  6082017 
Time Limit:  7 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions