#include using namespace std; const int sz = 302020; typedef long long ll; template void gi(Q &x){char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();} void pi(ll x){if (x > 9) pi(x / 10); putchar(x % 10 + 48);} int N; #define Root (N + 1) int q[sz], siz[sz], pfc[sz]; class Tree { public: int node[sz], next[sz], to[sz], e; ll w[sz]; int dep[sz], top[sz], par[sz]; ll d[sz]; void ins(int x, int y, ll v) {e++; next[e] = node[par[y] = x]; node[x] = e; to[e] = y; w[e] = v;} void bfs() { int i, j, k, l, r; q[l = r = 1] = Root; while (l <= r) for (j = node[k = q[l++]]; j; j = next[j]) { q[++r] = to[j]; dep[to[j]] = dep[k] + 1; d[to[j]] = d[k] + w[j]; } for (i = r; i; i--) { k = q[i]; siz[k] = 1; for (j = node[k]; j; j = next[j]) { siz[k] += siz[to[j]]; if (siz[to[j]] > siz[pfc[k]]) pfc[k] = to[j]; } } } int pos[sz], I; void dfs(int x) { pos[x] = ++I; if (x == Root) top[x] = x; if (pfc[x]) {top[pfc[x]] = top[x]; dfs(pfc[x]);} for (int j = node[x]; j; j = next[j]) if (pfc[x] != to[j]) top[to[j]] = to[j], dfs(to[j]); } int LCA(int x, int y) { while (top[x] != top[y]) if (dep[top[x]] >= dep[top[y]]) x = par[top[x]]; else y = par[top[y]]; if (dep[x] < dep[y]) return x; else return y; } ll dis(int x, int y){return d[x] + d[y] - (d[LCA(x, y)] << 1);} ll bit[sz]; void aa(int x, ll u){for (; x <= N + 1; x += x & -x) bit[x] += u;} ll s(int x){ll a = 0; for (; x; x -= x & -x) a += bit[x]; return a;} #define add(l, r, b) aa(l, b), aa((r) + 1, -b) void add_c(int x, int y, ll u) { while (top[x] != top[y]) if (dep[top[x]] >= dep[top[y]]) add(pos[top[x]], pos[x], u), x = par[top[x]]; else swap(x, y); if (dep[x] > dep[y]) swap(x, y); add(pos[x], pos[y], u); } #undef add ll query(int x) {return s(pos[x]);} } T[60]; //3 * 100000 #define huge 1000000000000000000ll #define right Right int bh[3][sz / 3], x[sz], y[sz]; ll down[2][sz / 3], right[3][sz / 3]; int par[sz]; int m, n, cq; pair Q[sz << 1]; #define mp make_pair int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0}; ll Dis(int x, int y, int d) { switch (d) { case 0 : return right[x][y - 1]; case 1 : return down[x][y]; case 2 : return right[x][y]; case 3 : return down[x - 1][y]; } } ll d[sz]; void dijk(int x1, int y1, int l, int r) { static int vis[sz], tttt; int s = bh[x1][y1], i, j, k, kx, ky, top = 1, nx, ny; Q[top] = mp(0, s); vis[s] = (tttt += 2) - 1; d[s] = 0; while (top) { pop_heap(Q + 1, Q + top + 1); k = Q[top--].second; kx = x[k]; ky = y[k]; if (vis[k] == tttt) continue; vis[k] = tttt; for (j = 0; j < 4; j++) { nx = kx + dx[j]; ny = ky + dy[j]; if (nx >= 0 && nx < m && ny >= l && ny <= r) { i = bh[nx][ny]; if (vis[i] <= tttt - 2) {vis[i] = tttt - 1; d[i] = huge;} ll w = d[k] + Dis(kx, ky, j); if (d[i] > w) { d[i] = w; par[i] = k; Q[++top] = mp(-d[i], i); push_heap(Q + 1, Q + top + 1); } } } } } int tmax; void crtree(int l, int r, int dep){ if (l > r) return; int md = (l + r) >> 1, i, j, k; for (i = 0; i < m; i++) { dijk(i, md, l, r); tmax = max(tmax, dep + i + 1); for (j = 0; j < m; j++) for (k = l; k <= r; k++) if (!(j == i && k == md)) T[dep + i].ins(par[bh[j][k]], bh[j][k], d[bh[j][k]] - d[par[bh[j][k]]]); } crtree(l, md - 1, dep + m); crtree(md + 1, r, dep + m); } void init() { int i, j; gi(m); gi(n); gi(cq); for (i = 0; i < m - 1; i++) for (j = 0; j < n; j++) gi(down[i][j]); for (i = 0; i < m; i++) for (j = 0; j < n - 1; j++) gi(right[i][j]); for (i = 0; i < m; i++) for (j = 0; j < n; j++) { bh[i][j] = ++N; x[N] = i; y[N] = j; } crtree(0, n - 1, 0); for (i = 0; i < tmax; i++) { for (j = 1; j <= N + 1; j++) pfc[j] = siz[j] = 0; for (j = 1; j <= N; j++) if (T[i].par[j] == 0) T[i].ins(Root, j, huge); T[i].bfs(); T[i].dfs(Root); } } void add(int s, int t, ll u) { int i, am; ll d, dm = huge; for (i = 0; i < tmax; i++) { d = T[i].dis(s, t); if (d < dm) dm = d, am = i; } T[am].add_c(s, t, u); } ll query(int x) { ll s = 0; for (int i = 0; i < tmax; i++) s += T[i].query(x); return s; } int main() { int c, x1, y1, x2, y2; ll u; init(); while (cq--) { gi(c); if (c == 1) { gi(x1); gi(y1); gi(x2); gi(y2); gi(u); add(bh[x1 - 1][y1 - 1], bh[x2 - 1][y2 - 1], u); } else { gi(x1); gi(y1); pi(query(bh[x1 - 1][y1 - 1])); putchar('\n'); } } return 0; }