#include "wombats.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 2000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001
using namespace std;
class intervalac {
int n;
vec<int> l, r;
vec<vec<vec<int>>> in;
int c;
vec<vec<int>> h, v;
public:
void postav(int x, vec<int>& h1, vec<int>& h2, vec<int>& v) {
For(i, c) {
//cout << "bol som c " << i << '\n';
priority_queue<pii> q;
vec<bool> bol(2 * c, 0);
q.push({ 0, i });
while (!q.empty()) {
int som = q.top().ss, d = q.top().ff; q.pop();
//cout << "bol som d " << som << ' ' << d << '\n';
if (som == 18 && d == 0 && i == 0) {
int lol = 1;
}
if (bol[som]) continue;
d *= (-1);
bol[som] = 1;
int nd = 0;
int pos = 0;
if (som >= c) {
pos = c;
swap(h1, h2);
}
int nsom = 0;
if (som + 1 - pos != c) {
nsom = som + 1;
nd = d + h1[nsom - pos - 1];
q.push({ (-1) * nd, nsom });
}
if (som - 1 - pos >= 0) {
nsom = som - 1;
nd = d + h1[nsom - pos];
q.push({ (-1) * nd, nsom });
}
if (som < c) {
nsom = som + c;
nd = d + v[som];
q.push({ (-1) * nd, nsom });
}
else {
in[x][i][som - c] = d;
}
if (som >= c) swap(h1, h2);
}
}
}
void update(int x) {
For(i, in[2 * x].size()) {
For(j, in[2 * x + 1].size()) {
in[x][i][j] = NEK;
For(r, in[2 * x].size()) {
in[x][i][j] = min(in[x][i][j], in[2 * x][i][r] + in[2 * x + 1][r][j]);
}
}
}
return;
}
void zaciatok(int r1, int c1, vec<vec<int>>& h1, vec<vec<int>>& v1) {
l.clear(); r.clear(); in.clear(); h.clear(); v.clear();
c = c1;
n = 1;
h = h1;
v = v1;
while (n < (r1-1)) n *= 2;
l.resize(2 * n); r.resize(2 * n);
if(h.size() < (n+1)) h.resize(n+1, vec<int>(c1 - 1, 0));
if(v.size() < n) v.resize(n, vec<int>(c1, 0));
in.resize(2 * n, vec<vec<int>>(c1, vec<int>(c1, NEK)));
For(i, n) {
l[i + n] = i;
r[i + n] = i;
postav(i+n, h[i], h[i + 1], v[i]);
}
rffor(i, 1, (n - 1)) {
l[i] = l[i * 2];
r[i] = r[i * 2 + 1];
update(i);
}
}
int daj(int a, int b) {
return in[1][a][b];
}
void zmenh(int p, int q, int w) {
h[p][q] = w;
if(p != (h.size() - 1)) postav(p+n, h[p], h[p + 1], v[p]);
if (p != 0) postav(p + n - 1, h[p - 1], h[p], v[p - 1]);
int som = p + n;
som /= 2;
while (som) {
update(som);
som /= 2;
}
return;
}
void zmenv(int p, int q, int w) {
v[p][q] = w;
postav(p + n, h[p], h[p + 1], v[p]);
int som = p + n;
som /= 2;
while (som) {
update(som);
som /= 2;
}
return;
}
};
intervalac seg;
vec<vec<int>> H, V;
vec<vec<int>> p;
int r, c;
set<int> umap;
struct policko {
int d, x, y;
bool operator<(const policko& other) const {
return d > other.d;
}
};
void vypocitaj(int s) {
p[s].resize(c, NEK);
priority_queue<policko> q;
q.push({ 0, 0, s });
vec<vec<bool>> bol(c, vec<bool>(c, 0));
while (!q.empty()) {
int d = q.top().d, x = q.top().x, y = q.top().y; q.pop();
if (bol[x][y]) continue;
bol[x][y] = 1;
if (y - 1 >= 0) {
q.push({ d + H[x][y-1], x, y - 1 });
}
if (y + 1 < c) {
q.push({ d + H[x][y], x, y + 1 });
}
if (x != r - 1) {
q.push({ d + V[x][y], x + 1, y });
}
else {
p[s][y] = d;
}
}
umap.insert(s);
return;
}
int escape(int v1, int v2) {
if (umap.find(v1) == umap.end()) {
vypocitaj(v1);
}
return p[v1][v2];
}
void changeH(int p1, int q1, int w) {
H[p1][q1] = w;
return;
}
void changeV(int p1, int q1, int w) {
V[p1][q1] = w;
umap.clear();
return;
}
void init(int R, int C, int H1[5000][200], int V1[5000][200]) {
r = R; c = C;
H.resize(r, vec<int>(c - 1, 0));
V.resize(r - 1, vec<int>(c, 0));
p.resize(c);
For(i, r) {
For(j, (c - 1)) {
H[i][j] = H1[i][j];
}
}
For(i, r - 1) {
For(j, c) {
V[i][j] = V1[i][j];
}
}
return;
}
/*
signed main() {
ll t;
//cin >> t;
t = 1;
For(w, t) {
int r, c;
cin >> r >> c;
int h[50][20];
int v[50][20];
For(i, r) {
For(j, (c-1)) {
cin >> h[i][j];
}
}
For(i, (r-1)) {
For(j, c) {
cin >> v[i][j];
}
}
init(r, c, h, v);
int e;
cin >> e;
For(i, e) {
int a, b, d;
cin >> a >> b >> d;
if (a == 1) {
int w; cin >> w;
changeH(b, d, w);
}
if (a == 2) {
int w; cin >> w;
changeV(b, d, w);
}
if (a == 3) {
int x = escape(b, d);
cout << x << '\n';
}
}
}
return 0;
}*/
