#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
int C;
struct Matrix{
int data[200][200];
Matrix (int x=0){
for (int i=0; i<C; ++i) for (int j=0; j<C; ++j) data[i][j]=x && i==j?0:inf;
}
auto & operator[](int x){ return data[x]; }
const auto & operator[](int x) const { return data[x]; }
Matrix operator*(const Matrix &a){
Matrix ans, opt;
for (int i=0; i<C; ++i){
ans[i][i]=-1;
for (int j=0; j<C; ++j){
if (ans[i][i]==-1 || ans[i][i]>min(inf, data[i][j]+a[j][i])){
ans[i][i]=min(inf, data[i][j]+a[j][i]);
opt[i][i]=j;
}
}
}
for (int d=1; d<C; ++d){
for (int i=0, j=d; j<C; ++i, ++j){
ans[i][j]=-1;
for (int k=opt[i][j-1]; k<=opt[i+1][j]; ++k){
if (ans[i][j]==-1 || ans[i][j]>min(inf, data[i][k]+a[k][j])){
ans[i][j]=min(inf, data[i][k]+a[k][j]);
opt[i][j]=k;
}
}
}
for (int i=d, j=0; i<C; ++i, ++j){
ans[i][j]=-1;
for (int k=opt[i-1][j]; k<=opt[i][j+1]; ++k){
if (ans[i][j]==-1 || ans[i][j]>min(inf, data[i][k]+a[k][j])){
ans[i][j]=min(inf, data[i][k]+a[k][j]);
opt[i][j]=k;
}
}
}
}
return ans;
}
};
struct Node{
Matrix data;
int tl, tr;
Node (){
tl=tr=-1;
}
};
struct SegmentTree{
int n;
vector<int> id;
vector<Node> t;
SegmentTree(){
t.emplace_back();
}
void init(int _n){
n=_n;
id.assign(n, 0);
}
void build(int k, int l, int r){
if (l==r){
id[l]=k;
return;
}
int mid=(l+r)>>1;
t[k].tl=t.size();
t.emplace_back();
t[k].tr=t.size();
t.emplace_back();
build(t[k].tl, l, mid);
build(t[k].tr, mid+1, r);
}
void build2(int k, int l, int r){
if (l==r) return;
int mid=(l+r)>>1;
build2(t[k].tl, l, mid);
build2(t[k].tr, mid+1, r);
t[k].data=t[t[k].tl].data*t[t[k].tr].data;
}
void update(int k, int l, int r, int pos){
if (l==r) return;
int mid=(l+r)>>1;
if (pos<=mid) update(t[k].tl, l, mid, pos);
else update(t[k].tr, mid+1, r, pos);
t[k].data=t[t[k].tl].data*t[t[k].tr].data;
}
} st;
const int SZ=10;
int R, H[5000][200], V[5000][200];
void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
R=_R, C=_C;
memcpy(H, _H, sizeof H);
memcpy(V, _V, sizeof V);
st.init((R+SZ-1)/SZ);
st.build(0, 0, st.n-1);
for (int il=0, ir=SZ-1; il<R; il+=SZ, ir+=SZ){
ir=min(ir, R-1);
Matrix cur(1), nxt;
for (int i=il; i<=ir; ++i){
for (int j=0; j<C; ++j){
int sum=0;
for (int k=j; k<C; ++k){
if (k!=j) sum+=H[i][k-1];
nxt[j][k]=sum+(i?V[i-1][j]:0);
nxt[k][j]=sum+(i?V[i-1][k]:0);
}
}
cur=cur*nxt;
}
st.t[st.id[il/SZ]].data=cur;
}
st.build2(0, 0, st.n-1);
}
void changeH(int P, int Q, int W) {
H[P][Q]=W;
int il=P/SZ*SZ, ir=min(il+SZ-1, R-1);
Matrix cur(1), nxt;
for (int i=il; i<=ir; ++i){
for (int j=0; j<C; ++j){
int sum=0;
for (int k=j; k<C; ++k){
if (k!=j) sum+=H[i][k-1];
nxt[j][k]=sum+(i?V[i-1][j]:0);
nxt[k][j]=sum+(i?V[i-1][k]:0);
}
}
cur=cur*nxt;
}
st.t[st.id[il/SZ]].data=cur;
st.update(0, 0, st.n-1, il/SZ);
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
int il=(P+1)/SZ*SZ, ir=min(il+SZ-1, R-1);
Matrix cur(1), nxt;
for (int i=il; i<=ir; ++i){
for (int j=0; j<C; ++j){
int sum=0;
for (int k=j; k<C; ++k){
if (k!=j) sum+=H[i][k-1];
nxt[j][k]=sum+(i?V[i-1][j]:0);
nxt[k][j]=sum+(i?V[i-1][k]:0);
}
}
cur=cur*nxt;
}
st.t[st.id[il/SZ]].data=cur;
st.update(0, 0, st.n-1, il/SZ);
}
int escape(int V1, int V2) {
return st.t[0].data[V1][V2];
}
