#include #include #include #include #include #include #include #include #include using namespace std; const long long INF = 1000000000000000000LL; const int MAXM = 3; const int MAXN = 100000; int m, n, q; long long goDown[MAXM][MAXN], goRight[MAXM][MAXN], dist[MAXM][MAXN]; pair pre[MAXM][MAXN]; bool mark[MAXM][MAXN]; struct Edge { int u, v; long long c; Edge(int u, int v, long long c) : u(u), v(v), c(c) { } }; inline int getID(int x, int y) { assert(0 <= x && x < m); assert(0 <= y && y < n); return x * n + y; } inline int lowbit(int x) { return x & -x; } struct Tree { int id; vector edges; vector>> children; vector dist, diff; vector size, heavy, top, depth, parent, index; int total, root; void add(int a, int b, int x, int y, long long c) { int u = getID(a, b); int v = getID(x, y); edges.push_back(Edge(u, v, c)); } void dfs(int u) { assert(0 <= u && u < depth.size()); assert(0 <= u && u < size.size()); assert(0 <= u && u < heavy.size()); size[u] = 1; heavy[u] = -1; for (const pair &edge : children[u]) { int v = edge.first; assert(0 <= v && v < size.size()); assert(size[v] == 0); assert(0 <= v && v < depth.size()); depth[v] = depth[u] + 1; assert(0 <= v && v < dist.size()); dist[v] = dist[u] + edge.second; assert(0 <= v && v < parent.size()); parent[v] = u; dfs(v); size[u] += size[v]; if (heavy[u] == -1 || size[v] > size[heavy[u]]) { heavy[u] = v; } } } void getTopNode(int u) { assert(0 <= u && u <= root); assert(0 <= u && u < index.size()); index[u] = ++ total; if (heavy[u] != -1) { int v = heavy[u]; assert(0 <= v && v < top.size()); top[v] = top[u]; getTopNode(v); } for (const pair &edge : children[u]) { int v = edge.first; if (v == heavy[u]) { continue; } top[v] = v; getTopNode(v); } } int getLCA(int u, int v) const { while (top[u] != top[v]) { if (depth[top[u]] >= depth[top[v]]) { u = parent[top[u]]; } else { v = parent[top[v]]; } } return depth[u] < depth[v] ? u : v; } long long getDist(int u, int v) const { return dist[u] + dist[v] - 2 * dist[getLCA(u, v)]; } void finalize() { assert(edges.size() <= n * m - 1); root = n * m; children = vector>>(root + 1); index = parent = depth = size = top = heavy = vector(root + 1); dist = vector(root + 1); diff = vector(root + 2); vector isRoot(n * m, true); for (const Edge &edge : edges) { assert(edge.u >= 0 && edge.u < root); assert(edge.v >= 0 && edge.v < root); children[edge.v].push_back(make_pair(edge.u, edge.c)); isRoot[edge.u] = false; } int roots = 0; for (int i = 0; i < n * m; ++ i) { if (isRoot[i]) { ++ roots; children[root].push_back(make_pair(i, INF)); } } assert(roots + edges.size() == n * m); dfs(root); // cerr << " dfs done" << endl; total = 0; top[root] = root; getTopNode(root); // cerr << " getTopNode done" << endl; assert(total == root + 1); } void add(int x, long long delta) { if (x >= diff.size()) { return; } assert(1 <= x && x < diff.size()); for (int y = x; y < diff.size(); y += lowbit(y)) { diff[y] += delta; } } long long getSum(int x) const { assert(1 <= x && x < diff.size()); long long ret = 0; for (int y = x; y > 0; y -= lowbit(y)) { ret += diff[y]; } return ret; } // diff[i] = a[i] - a[i - 1] void add(int u, int v, long long c) { while (top[u] != top[v]) { if (depth[top[u]] >= depth[top[v]]) { int l = index[top[u]]; int r = index[u]; assert(l <= r); add(r + 1, -c); add(l, c); u = parent[top[u]]; } else { int l = index[top[v]]; int r = index[v]; assert(l <= r); add(r + 1, -c); add(l, c); v = parent[top[v]]; } } int l = index[u]; int r = index[v]; if (l > r) { swap(l, r); } assert(l <= r); add(r + 1, -c); add(l, c); } long long query(int u) const { return getSum(index[u]); } }; inline void update(int x, int y, int tx, int ty, long long c, queue> &q) { if (dist[tx][ty] > dist[x][y] + c) { dist[tx][ty] = dist[x][y] + c; pre[tx][ty] = make_pair(x, y); if (!mark[tx][ty]) { mark[tx][ty] = true; q.push(make_pair(tx, ty)); if (dist[q.front().first][q.front().second] > dist[tx][ty]) { swap(q.front(), q.back()); } } } } void constructTree(int l, int r, int sx, int sy, Tree &tree) { queue> q; q.push(make_pair(sx, sy)); for (int i = 0; i < m; ++ i) { for (int j = l; j <= r; ++ j) { dist[i][j] = INF; mark[i][j] = false; } } dist[sx][sy] = 0; mark[sx][sy] = true; while (q.size()) { int x = q.front().first, y = q.front().second; mark[x][y] = false; q.pop(); if (x + 1 < m) { long long c = goDown[x][y]; int tx = x + 1, ty = y; update(x, y, tx, ty, c, q); } if (x - 1 >= 0) { long long c = goDown[x - 1][y]; int tx = x - 1, ty = y; update(x, y, tx, ty, c, q); } if (y + 1 <= r) { long long c = goRight[x][y]; int tx = x, ty = y + 1; update(x, y, tx, ty, c, q); } if (y - 1 >= l) { long long c = goRight[x][y - 1]; int tx = x, ty = y - 1; update(x, y, tx, ty, c, q); } } for (int i = 0; i < m; ++ i) { for (int j = l; j <= r; ++ j) { if (i != sx || j != sy) { assert(dist[i][j] < INF); int x = pre[i][j].first, y = pre[i][j].second; tree.add(i, j, x, y, dist[i][j] - dist[x][y]); } } } } vector trees; void constructTrees(int l, int r, int start) { if (l > r) { return; } int mid = l + r >> 1; while (trees.size() < start + m) { trees.push_back(Tree()); } for (int i = 0; i < m; ++ i) { constructTree(l, r, i, mid, trees[start + i]); } constructTrees(l, mid - 1, start + m); constructTrees(mid + 1, r, start + m); } int main() { assert(scanf("%d%d%d", &m, &n, &q) == 3); assert(1 <= m && m <= 3); assert(1 <= n && n <= MAXN); assert(1 <= q && q <= MAXN); for (int i = 0; i + 1 < m; ++ i) { for (int j = 0; j < n; ++ j) { assert(scanf("%lld", &goDown[i][j]) == 1); assert(1 <= goDown[i][j] && goDown[i][j] <= INF); } } for (int i = 0; i < m; ++ i) { for (int j = 0; j + 1 < n; ++ j) { assert(scanf("%lld", &goRight[i][j]) == 1); assert(1 <= goRight[i][j] && goRight[i][j] <= INF); } } cerr << "read " << n << " " << m << endl; constructTrees(0, n - 1, 0); cerr << "constructed" << endl; int ptr = 0; for (Tree& tree : trees) { tree.finalize(); tree.id = ptr ++; } cerr << "# of trees = " << trees.size() << endl; while (q --) { int op; assert(scanf("%d", &op) == 1); assert(op == 1 || op == 2); if (op == 1) { int i1, j1, i2, j2; long long c; assert(scanf("%d%d%d%d%lld", &i1, &j1, &i2, &j2, &c) == 5); assert(1 <= c && c <= 10000000000000LL); assert(1 <= i1 && i1 <= m); assert(1 <= i2 && i2 <= m); -- i1; -- i2; assert(1 <= j1 && j1 <= n); assert(1 <= j2 && j2 <= n); -- j1; -- j2; int u = getID(i1, j1), v = getID(i2, j2); long long minDist = INF; int bestTree = -1; for (const Tree& tree : trees) { long long dist = tree.getDist(u, v); if (dist < minDist) { minDist = dist; bestTree = tree.id; } } trees[bestTree].add(u, v, c); } else { int i, j; assert(scanf("%d%d", &i, &j) == 2); assert(1 <= i && i <= 3); assert(1 <= j && j <= n); -- i; -- j; int u = getID(i, j); long long answer = 0; for (const Tree& tree : trees) { //cerr << " tree " << tree.id << ": index = " << tree.index[u] << ", value = " << tree.query(u) << endl; answer += tree.query(u); } printf("%lld\n", answer); } } return 0; }