#include <bits/stdc++.h>
#include "wombats.h"
template <class T> using Vec = std::vector<T>;
int Type, Vsum;
Vec<Vec<int>> vert, side;
Vec<std::array<std::array<int, 2>, 2>> pos;
struct SemiGroup {
std::array<std::array<int, 2>, 2> dist;
int right;
SemiGroup operator + (const SemiGroup& other) const {
std::array<std::array<int, 2>, 2> ret;
for (auto& v: ret) {
v.fill(1000000000);
}
for (int i = 0; i < 2; ++i) {
for (int k = 0; k < 2; ++k) {
for (int j = 0; j < 2; ++j) {
ret[i][j] = std::min(ret[i][j], dist[i][k] + vert[right][k] + other.dist[k][j]);
}
}
}
return SemiGroup { std::move(ret), other.right };
}
};
using Monoid = std::optional<SemiGroup>;
constexpr Monoid zero() { return std::nullopt; }
Monoid operator + (const Monoid& l, const Monoid& r) {
if (!l) return r;
if (!r) return l;
return *l + *r;
}
int ceil_log2(const int x) {
int e = 0;
while ((1 << e) < x) e += 1;
return e;
}
struct Segtree {
Vec<Monoid> data;
Segtree() = default;
Segtree(const int n): data(1 << (ceil_log2(n) + 1), zero()) {}
void assign(int i, const Monoid& m) {
i += data.size() / 2;
data[i] = m;
while (i > 1) {
i >>= 1;
data[i] = data[2 * i] + data[2 * i + 1];
}
}
Monoid fold() { return data[1]; }
} seg;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
vert = Vec<Vec<int>>(R - 1, Vec<int>(C));
for (int i = 0; i < R - 1; ++i) {
for (int j = 0; j < C; ++j) {
vert[i][j] = V[i][j];
}
}
side = Vec<Vec<int>>(R, Vec<int>(C - 1));
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C - 1; ++j) {
side[i][j] = H[i][j];
}
}
if (C == 1) {
Type = 1;
for (int i = 0; i < R - 1; ++i) {
Vsum += vert[i][0];
}
}
else if (C == 2) {
Type = 2;
seg = Segtree(R);
pos.resize(R);
for (int i = 0; i < R; ++i) {
pos[i][0][0] = pos[i][1][1] = 0;
pos[i][0][1] = pos[i][1][0] = side[i][0];
seg.assign(i, SemiGroup{pos[i], i});
}
}
else if (R <= 20 and C <= 20) {
Type = 3;
}
else {
Type = 4;
}
}
void changeH(int P, int Q, int W) {
if (Type == 2) {
const int i = P;
side[i][0] = W;
pos[i][0][0] = pos[i][1][1] = 0;
pos[i][0][1] = pos[i][1][0] = side[i][0];
seg.assign(i, SemiGroup{pos[i], i});
}
else {
side[P][Q] = W;
}
}
void changeV(int P, int Q, int W) {
if (Type == 1) {
Vsum -= vert[P][Q];
Vsum += W;
vert[P][Q] = W;
}
else if (Type == 2) {
vert[P][Q] = W;
seg.assign(P, SemiGroup{pos[P], P});
}
else {
vert[P][Q] = W;
}
}
int escape(int V1, int V2) {
if (Type == 1) {
return Vsum;
}
else if (Type == 2) {
return seg.fold() -> dist[V1][V2];
}
else if (Type == 3) {
static Vec<Vec<int>> dist;
static bool first = true;
if (first) {
const int R = (int) side.size();
const int C = (int) side[0].size() + 1;
dist = Vec<Vec<int>>(C, Vec<int>(C));
for (int i = 0; i < C; ++i) {
int sum = 0;
for (int j = i; j < C; ++j) {
dist[i][j] = dist[j][i] = sum;
if (j != C - 1) {
sum += side[0][j];
}
}
}
for (int i = 0; i < R - 1; ++i) {
Vec<Vec<int>> merge(C, Vec<int>(C));
for (int j = 0; j < C; ++j) {
int sum = 0;
for (int k = j; k < C; ++k) {
merge[j][k] = merge[k][j] = sum;
if (k != C - 1) {
sum += side[i + 1][k];
}
}
}
Vec<Vec<int>> next(C, Vec<int>(C, 1000000000));
for (int j = 0; j < C; ++j) {
for (int k = 0; k < C; ++k) {
for (int l = 0; l < C; ++l) {
next[j][l] = std::min(next[j][l], dist[j][k] + vert[i][k] + merge[k][l]);
}
}
}
dist = std::move(next);
}
first = false;
}
return dist[V1][V2];
}
else {
const int R = (int) side.size();
const int C = (int) side[0].size() + 1;
Vec<int> dist(C);
Vec<int> sum(C);
for (int i = 0; i < C - 1; ++i) {
sum[i + 1] = sum[i] + side[0][i];
}
for (int j = 0; j < C; ++j) {
dist[j] = std::abs(sum[V1] - sum[j]);
}
for (int i = 0; i < R - 1; ++i) {
for (int j = 0; j < C; ++j) {
dist[j] += vert[i][j];
}
sum[0] = 0;
for (int j = 0; j < C - 1; ++j) {
sum[j + 1] = sum[j] + side[i + 1][j];
}
int lmin = 1000000000;
for (int j = 0; j < C; ++j) {
dist[j] = std::min(dist[j], lmin + sum[j]);
lmin = std::min(lmin, dist[j] - sum[j]);
}
int rmin = 1000000000 + 1000000000;
for (int j = C - 1; j >= 0; --j) {
dist[j] = std::min(dist[j], rmin - sum[j]);
rmin = std::min(rmin, dist[j] + sum[j]);
}
}
return dist[V2];
}
}
