#include"wombats.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct node
{
int l,r;
int d[200][200];
}tr[1500];
int r,c;
int opt[200][200];
inline void merge(node&m,node&x,node&y)
{
for(int i=0;i<c;i++)
for(int j=0;j<c;j++)
opt[i][j]=-1;
int&o0=opt[0][0]=0;
m.d[0][0]=x.d[0][o0]+y.d[0][o0];
for(int k=0;++k<c;)
if(x.d[0][k]+y.d[k][0]<x.d[0][o0]+y.d[o0][0])
o0=k,m.d[0][0]=x.d[0][o0]+y.d[o0][0];
for(int i=1;i<c;i++)
{
int j=0;
int&o=opt[i][j]=opt[i-1][j];
m.d[i][j]=x.d[i][o]+y.d[o][j];
for(int k=o;++k<c;)
if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j])
o=k,m.d[i][j]=x.d[i][o]+y.d[o][j];
}
for(int j=1;j<c;j++)
{
int i=c-1;
int&o=opt[i][j]=opt[i][j-1];
m.d[i][j]=x.d[i][o]+y.d[o][j];
for(int k=o;++k<c;)
if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j])
o=k,m.d[i][j]=x.d[i][o]+y.d[o][j];
}
for(int l=-c;++l<c;)
{
for(int i=0;i<c;i++)
{
int j=i+l;
if(j<0||j>=c||opt[i][j]!=-1)
continue;
int&o=opt[i][j]=opt[i][j-1];
m.d[i][j]=x.d[i][o]+y.d[o][j];
for(int k=o;++k<=opt[i+1][j];)
if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j])
o=k,m.d[i][j]=x.d[i][o]+y.d[o][j];
}
}
return;
}
vector<vector<int> >h,v;
inline void init(int n,int s,int e)
{
node&x=tr[n];
node t,p;
vector<int>ps(c,0);
for(int i=1;i<c;i++)
ps[i]=ps[i-1]+h[s][i-1];
for(int i=0;i<c;i++)
for(int j=0;j<c;j++)
x.d[i][j]=i>j?ps[i]-ps[j]:ps[j]-ps[i];
for(int r=s;r<e;r++)
{
p=x;
for(int i=0;i<c;i++)
for(int j=0;j<c;j++)
p.d[i][j]+=v[r][j];
for(int i=1;i<c;i++)
ps[i]=ps[i-1]+h[r+1][i-1];
for(int i=0;i<c;i++)
for(int j=0;j<c;j++)
t.d[i][j]=i>j?ps[i]-ps[j]:ps[j]-ps[i];
merge(x,p,t);
}
return;
}
int tct=0,rt;
int init(int s,int e)
{
int cur=tct++;
node&x=tr[cur];
if(e-s<15)
{
x.l=x.r=0;
init(cur,s,e);
return cur;
}
int m=(s+e)/2;
x.l=init(s,m);
x.r=init(m,e);
merge(x,tr[x.l],tr[x.r]);
return cur;
}
void ch(int n,int s,int e,int r)
{
if(s>r||e<r)
return;
node&x=tr[n];
if(e-s<15)
{
init(n,s,e);
return;
}
int m=(s+e)/2;
ch(x.l,s,m,r);
ch(x.r,m,e,r);
merge(x,tr[x.l],tr[x.r]);
return;
}
void cv(int n,int s,int e,int r)
{
if(s>r||e<=r)
return;
node&x=tr[n];
if(e-s<15)
{
init(n,s,e);
return;
}
int m=(s+e)/2;
cv(x.l,s,m,r);
cv(x.r,m,e,r);
merge(x,tr[x.l],tr[x.r]);
return;
}
void init(int R,int C,int H[5000][200],int V[5000][200])
{
r=R;
c=C;
h.resize(r);
for(int i=0;i<r;i++)
for(int j=0;j<c-1;j++)
h[i].eb(H[i][j]);
v.resize(r-1);
for(int i=0;i<r-1;i++)
for(int j=0;j<c;j++)
v[i].eb(V[i][j]);
rt=init(0,r-1);
return;
}
void changeH(int P,int Q,int W)
{
h[P][Q]=W;
ch(rt,0,r-1,P);
return;
}
void changeV(int P,int Q,int W)
{
v[P][Q]=W;
cv(rt,0,r-1,P);
return;
}
int escape(int V1,int V2)
{
return tr[rt].d[V1][V2];
}
