{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problems statements in \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/SEPT17/mandarin/QGRID.pdf\"\u003emandarin chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/SEPT17/russian/QGRID.pdf\"\u003erussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/SEPT17/vietnamese/QGRID.pdf\"\u003evietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\n\u003cp\u003eChef 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: \u003c/p\u003e\r\n\r\n\u003cp\u003e Consider an \u003cb\u003eM × N\u003c/b\u003e 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 \u003cb\u003e(i,j)\u003c/b\u003e associated with it, where \u003cb\u003e1 ≤ i ≤ M\u003c/b\u003e is its row, and \u003cb\u003e1 ≤ j ≤ N\u003c/b\u003e is its column. There are two types of edges in a grid graph(note that all edges are bidirectional) :\u003c/p\u003e\r\n\u003cul\u003e\r\n\t\u003cli\u003eWhen \u003cb\u003ei \u003c M\u003c/b\u003e, there is an edge of weight \u003cb\u003edown(i, j)\u003c/b\u003e connecting \u003cb\u003e(i, j)\u003c/b\u003e and \u003cb\u003e(i+1, j)\u003c/b\u003e;\u003c/li\u003e\r\n\t\u003cli\u003eWhen \u003cb\u003ej \u003c N\u003c/b\u003e, there is an edge of weight \u003cb\u003eright(i, j)\u003c/b\u003e connecting \u003cb\u003e(i, j)\u003c/b\u003e and \u003cb\u003e(i, j+1)\u003c/b\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\r\n\tInitially, every vertex has a weight of zero.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tDefine the length of a path to be the sum of weights of all the edges in this path. The shortest path between \u003cb\u003e(i1, j1)\u003c/b\u003e and \u003cb\u003e(i2, j2)\u003c/b\u003e is the path with the minimum length. Of course, the weights associated with vertices doesn\u0027t influence shortest paths at all.\u003c/p\u003e\r\n\u003cp\u003e\r\nThe task in the problem is to process the following 2 types of queries on this graph efficiently :\u003c/p\u003e\r\n\u003cul\u003e\r\n\t\u003cli\u003e\u003cb\u003ei1\u003c/b\u003e \u003cb\u003ej1\u003c/b\u003e \u003cb\u003ei2\u003c/b\u003e \u003cb\u003ej2\u003c/b\u003e \u003cb\u003ec\u003c/b\u003e : add \u003cb\u003ec\u003c/b\u003e to the weights of all vertices in the shortest path between \u003cb\u003e(i1, j1)\u003c/b\u003e and \u003cb\u003e(i2, j2)\u003c/b\u003e.\u003c/li\u003e\r\n\t\u003cli\u003e\u003cb\u003ei\u003c/b\u003e \u003cb\u003ej\u003c/b\u003e : return the weight of vertex \u003cb\u003e(i, j)\u003c/b\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003cp\u003eChef is confused with the problem but he wants to help the child. Can you help Chef with this problem?\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003e\r\nThe first line contains three integers \u003cb\u003eM, N, Q\u003c/b\u003e. \u003cb\u003eM\u003c/b\u003e and \u003cb\u003eN\u003c/b\u003e denotes the graph\u0027s size; \u003cb\u003eQ\u003c/b\u003e denotes the number of queries.\u003c/p\u003e\r\n\u003cp\u003eNext \u003cb\u003eM - 1\u003c/b\u003e lines, each line contains \u003cb\u003eN\u003c/b\u003e numbers. The \u003cb\u003ej\u003c/b\u003e-th number in the \u003cb\u003ei\u003c/b\u003e-th line in this part(i.e., the \u003cb\u003e(i + 1)\u003c/b\u003e-th line in total) denotes \u003cb\u003edown(i, j)\u003c/b\u003e.\u003c/p\u003e\r\n\u003cp\u003eNext \u003cb\u003eM\u003c/b\u003e lines, each line contains \u003cb\u003eN - 1\u003c/b\u003e numbers. The \u003cb\u003ej\u003c/b\u003e-th number in the \u003cb\u003ei\u003c/b\u003e-th line in this part(i.e., the \u003cb\u003e(i + M)\u003c/b\u003e-th line in total) denotes \u003cb\u003eright(i, j)\u003c/b\u003e.\u003c/p\u003e\r\n\u003cp\u003eNext \u003cb\u003eQ\u003c/b\u003e lines, each line contains 3 or 6 numbers, denoting a query.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each query of type 2, output the weight of required vertex.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\t\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eM\u003c/b\u003e ≤ \u003cb\u003e3\u003c/b\u003e\u003c/li\u003e\r\n\t\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\t\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eQ\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\t\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003edown(i,j), right(i,j)\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e12\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\t\u003cli\u003eIn type 1 query :\r\n\t\t\u003cul\u003e\r\n\t\t\t\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003ei1, i2\u003c/b\u003e ≤ \u003cb\u003eM\u003c/b\u003e\u003c/li\u003e\r\n\t\t\t\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003ej1, j2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\r\n\t\t\t\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003ec\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e13\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\t\t\t\u003cli\u003eThe shortest path between \u003cb\u003e(i1, j1)\u003c/b\u003e and \u003cb\u003e(i2, j2)\u003c/b\u003e is \u003cb\u003eunique\u003c/b\u003e.\u003c/li\u003e\r\n\t\t\u003c/ul\u003e\r\n\t\u003c/li\u003e\r\n\t\u003cli\u003eIn type 2 query :\r\n\t\t\u003cul\u003e\r\n\t\t\t\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003ei\u003c/b\u003e ≤ \u003cb\u003eM\u003c/b\u003e\u003c/li\u003e\r\n\t\t\t\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003ej\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\r\n\t\t\u003c/ul\u003e\r\n\t\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eSubtasks\u003c/h3\u003e\r\n\u003cul\u003e\r\n\t\u003cli\u003e\u003cb\u003eSubtask #1 (6 points)\u003c/b\u003e: \u003cb\u003eN, Q ≤ 10\u003csup\u003e3\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\t\u003cli\u003e\u003cb\u003eSubtask #2: (11 points)\u003c/b\u003e: \u003cb\u003eM \u003d 1\u003c/b\u003e.\u003c/li\u003e\r\n\t\u003cli\u003e\u003cb\u003eSubtask #3: (30 points)\u003c/b\u003e: \u003cb\u003eM \u003d 2\u003c/b\u003e.\u003c/li\u003e\r\n\t\u003cli\u003e\u003cb\u003eSubtask #4: (24 points)\u003c/b\u003e: \t\r\n\t\t\u003cul\u003e\r\n\t\t\t\u003cli\u003e\u003cb\u003edown(i,j)\u003c/b\u003e and \u003cb\u003eright(i,j)\u003c/b\u003e are uniformly randomly generated from \u003cb\u003e[1,3 × 10\u003csup\u003e10\u003c/sup\u003e]\u003c/b\u003e.\u003c/li\u003e\r\n\t\t\t\u003cli\u003eQueries are also randomly generated.\u003c/li\u003e\r\n\t\t\t\u003cli\u003eThere is only one test file for this subtask.\u003c/li\u003e\r\n\t\t\u003c/ul\u003e\r\n\t\u003c/li\u003e\r\n\t\u003cli\u003e\u003cb\u003eSubtask #5: (29 points):\u003c/b\u003e: Original Constraints\u003c/li\u003e\r\n\u003c/ul\u003e"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3 11\r\n1 1 5\r\n2 10 6\r\n1 4\r\n1 13\r\n6 5\r\n1 2 2 3 3 1\r\n1 2 2 1 3 2\r\n2 1 1\r\n2 1 2\r\n2 1 3\r\n2 2 1\r\n2 2 2\r\n2 2 3\r\n2 3 1\r\n2 3 2\r\n2 3 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n2\r\n2\r\n1\r\n3\r\n0\r\n1\r\n1\r\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}