#include "wombats.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
const int inf=1e9;
int dist[300][202][202],costv[5005][202],costh[5005][200];
int n,m;
int pref[202],root,bound;
int ans[202][202],what[202][202];
void mul(vector<vector<int>>a,vector<vector<int>>b){
//knuth's op
vector<vector<int>>opt(m,vector<int>(m,-1));
for(int i=0;i<m;i++)for(int j=0;j<m;j++)what[i][j]=inf,opt[i][i]=i;
for(int i=0;i<m;i++){
for(int j=m-1;j>=0;j--){
int x=0,y=m-1;
if(i&&opt[i-1][j]!=-1)x=opt[i-1][j];
if(j+1<m&&opt[i][j+1]!=-1)y=opt[i][j+1];
for(int k=x;k<=y;k++)if(what[i][j]>a[i][k]+b[k][j]){
what[i][j]=a[i][k]+b[k][j];
opt[i][j]=k;
}
}
}
}
struct seg{
vector<vector<int>>v[1000];
void build(int l,int r,int pos){
v[pos].resize(m,vector<int>(m));
int mid=l+(r-l)/2;
if(l==r){
for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=dist[l][i][j];
return;
}
build(l,mid,pos*2);
build(mid+1,r,pos*2+1);
mul(v[pos*2],v[pos*2+1]);
for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=what[i][j];
}
void update(int l,int r,int qpos,int pos){
int mid=l+(r-l)/2;
if(l==r){
for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=dist[l][i][j];
return;
}
if(qpos<=mid)update(l,mid,qpos,pos*2);
else update(mid+1,r,qpos,pos*2+1);
mul(v[pos*2],v[pos*2+1]);
for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=what[i][j];
}
}t;
void cal(int id){
for(int st=0;st<m;st++)for(int go=0;go<m;go++){
if(st!=go)dist[id][st][go]=inf;
else dist[id][st][go]=0;
}
for(int r=(id*root);r<min(n,(id*root)+root);r++)for(int st=0;st<m;st++){
int mncost=inf,add=0;
for(int go=0;go<m;go++){
mncost=min(mncost,dist[id][st][go]-add);
pref[go]=mncost+add;
add+=costh[r][go];
}
mncost=inf,add=0;
for(int go=m-1;go>=0;go--){
mncost=min(mncost,dist[id][st][go]-add);
dist[id][st][go]=min(pref[go],mncost+add);
if(r!=n-1)dist[id][st][go]+=costv[r][go];
if(go)add+=costh[r][go-1];
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
n=R,m=C;
//root=sqrt(n);
root=60;
bound=((n-1)/root);
for(int i=0;i<n;i++)for(int j=0;j<m-1;j++)costh[i][j]=H[i][j];
for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)costv[i][j]=V[i][j];
for(int i=0;i<=bound;i++)cal(i);
t.build(0,bound,1);
}
void changeH(int P, int Q, int W){
costh[P][Q]=W;
cal(P/root);
t.update(0,bound,P/root,1);
}
void changeV(int P, int Q, int W){
costv[P][Q]=W;
cal(P/root);
t.update(0,bound,P/root,1);
}
int escape(int V1, int V2){
return t.v[1][V1][V2];
}
//70x200x200x500
/*
we can compute [start][at][row]
=200x200x5000
for each update
how to improve?
use segtree? and matrix [from][go] 200x200
too much memory?
do sqrt decomp instead? trading time for space
split block
what if we combine both sqrt and segtree 'o'?
we can do qry in
*/
