/*
ID: varunra2
LANG: C++
TASK: wombat
*/
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
int n, m;
int siz;
int hsh(int i, int j) { return i * m + j; }
PII unhsh(int h) { return MP(h / m, h % m); }
VVI h(5000, VI(200));
VVI v(5000, VI(200));
vector<VII> adj;
void addEdge(int i, int j, int k, int l, int w, bool b = false) {
int u = hsh(i, j);
int v = hsh(k, l);
adj[u].PB(MP(v, w));
if (b) adj[v].PB(MP(u, w));
}
void genAdj() {
adj.resize(siz);
trav(x, adj) x.clear();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
addEdge(i, j, i + 1, j, v[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
addEdge(i, j, i, j + 1, h[i][j], true);
}
}
}
int dijk(int src, int goal) {
VI dist(siz, 2 * INF);
dist[src] = 0;
priority_queue<PII, VII, greater<PII>> pq;
pq.push(MP(0, src));
vector<bool> vis(siz, false);
while (!pq.empty()) {
int u = pq.top().y;
int d = pq.top().x;
if (u == goal) return d;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto& x : adj[u]) {
if (dist[u] + x.y < dist[x.x]) {
dist[x.x] = dist[u] + x.y;
pq.push(MP(dist[x.x], x.x));
}
}
}
return 2 * INF;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R;
m = C;
siz = n * m;
for (int i = 0; i < 5000; i++) {
for (int j = 0; j < 200; j++) {
h[i][j] = H[i][j];
v[i][j] = V[i][j];
}
}
genAdj();
}
void changeV(int p, int q, int w) {
v[p][q] = w;
genAdj();
}
void changeH(int p, int q, int w) {
h[p][q] = w;
genAdj();
}
int escape(int a, int b) { return dijk(hsh(0, a), hsh(n - 1, b)); }
// int main() {
// #ifndef ONLINE_JUDGE
// freopen("wombat.in", "r", stdin);
// freopen("wombat.out", "w", stdout);
// #endif
// cin.sync_with_stdio(0);
// cin.tie(0);
// int r, c;
// int h[5000][200];
// int v[5000][200];
// cin >> r >> c;
// rep(i, 0, r) rep(j, 0, c - 1) cin >> h[i][j];
// rep(i, 0, r - 1) rep(j, 0, c) cin >> v[i][j];
// init(r, c, h, v);
// debug("done");
// int q;
// cin >> q;
// while (q--) {
// int type;
// cin >> type;
// if (type == 0) {
// int a, b;
// cin >> a >> b;
// cout << escape(a, b) << '\n';
// } else if (type == 1) {
// int p, q, w;
// cin >> p >> q >> w;
// changeV(p, q, w);
// } else {
// int p, q, w;
// cin >> p >> q >> w;
// changeH(p, q, w);
// }
// debug("done");
// }
// return 0;
// }
