#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 {
Type = 3;
}
}
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 {
}
}
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 {
}
}
int escape(int V1, int V2) {
if (Type == 1) {
return Vsum;
}
else if (Type == 2) {
return seg.fold() -> dist[V1][V2];
}
else {
}
}
