#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
constexpr int inf = 1e9;
int n, m;
vector<vector<int>> h, v;
vector<multiset<pair<int, int>>> g;
vector<int> d0, d1;
void dijkstra(int s, vector<int> &d) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
d.assign(n * m, inf);
vector<bool> vis(n * m);
d[s] = 0;
q.push({0, s});
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w] : g[u]) {
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push({d[v], v});
}
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R; m = C;
h.resize(n, vector<int>(m - 1));
v.resize(n - 1, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j < m - 1) {
h[i][j] = H[i][j];
}
if (i < n - 1) {
v[i][j] = V[i][j];
}
}
}
g.resize(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
int k = i * m + j;
g[k].insert({k + 1, h[i][j]});
g[k + 1].insert({k, h[i][j]});
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
int k = i * m + j;
g[k].insert({k + m, v[i][j]});
}
}
}
bool upd = 1;
void changeH(int i, int j, int w) {
upd = 1;
int k = i * m + j;
g[k + 1].erase(g[k + 1].find({k, h[i][j]}));
g[k].erase(g[k].find({k + 1, h[i][j]}));
h[i][j] = w;
g[k].insert({k + 1, h[i][j]});
g[k + 1].insert({k, h[i][j]});
}
void changeV(int i, int j, int w) {
upd = 1;
int k = i * m + j;
g[k].erase(g[k].find({k + m, v[i][j]}));
v[i][j] = w;
g[k].insert({k + m, v[i][j]});
}
int escape(int s, int t) {
if (upd) {
dijkstra(0, d0);
dijkstra(1, d1);
upd = 0;
}
t += (n - 1) * m;
if (s == 0) {
return d0[t];
} else {
return d1[t];
}
}
