#include <bits/stdc++.h>
#include "wombats.h"
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=1e5+100,M=60;
ll L[N*M],R[N*M],seg[N*M];
ll ts=1;
ll root[210];
int add(ll nod,ll l,ll r,ll le,ll re,ll val){
// cout << nod << " " << l << " " << r << " " << le << endl;
if (l>=re || le>=r) return nod;
ll NOD=ts;
ts++;
L[NOD]=L[nod];
R[NOD]=R[nod];
seg[NOD]=seg[nod];
if (l>=le && r<=re){
seg[NOD]+=val;
return NOD;
}
ll mid=(r+l)/2;
L[NOD]=add(L[NOD],l,mid,le,re,val);
R[NOD]=add(R[NOD],mid,r,le,re,val);
return NOD;
}
void shift(ll nod){
seg[ts]=seg[L[nod]];
L[ts]=L[L[nod]];
R[ts]=R[L[nod]];
L[nod]=ts;
seg[ts]+=seg[nod];
ts++;
seg[ts]=seg[R[nod]];
L[ts]=L[R[nod]];
R[ts]=R[R[nod]];
R[nod]=ts;
seg[ts]+=seg[nod];
ts++;
seg[nod]=0;
}
void cop(ll nod1,ll nod2,ll l,ll r,ll le,ll re){
if (l>=re || le>=r) return ;
if (l>=le && r<=re){
L[nod1]=L[nod2];
R[nod1]=R[nod2];
seg[nod1]=seg[nod2];
return ;
}
shift(nod1);
shift(nod2);
ll mid=(r+l)/2;
cop(L[nod1],L[nod2],l,mid,le,re);
cop(R[nod1],R[nod2],mid,r,le,re);
}
ll get(ll nod,ll l,ll r,ll id){
if (r-l==1) return seg[nod];
ll mid=(r+l)/2;
ll ans=seg[nod];
if (mid>id) ans+=get(L[nod],l,mid,id);
else ans+=get(R[nod],mid,r,id);
return ans;
}
int n,m;
int h[5000][200],v[5000][200];
void solve(int RR, int C) {
/* ... */
ts=1;
for (int i=0;i<N*M;i++) L[i]=0,R[i]=0,seg[i]=0;
for (int i=0;i<m;i++){
root[i]=ts;
ts++;
}
for (int i=0;i<m;i++){
for (int j=0;j<m;j++){
// cout << j << endl;
if (j!=i) root[i]=add(root[i],0,m,j,j+1,(ll)1e9);
}
}
shift(root[1]);
// cout << get(root[1],0,m,0) << endl;
// cout << "GOOZ" << endl;
for (int ii=0;ii<RR;ii++){
/// az samt chap update shavad
for (int i=1;i<m;i++){
ll l=-1,r=m;
while(r-l>1){
ll mid=(r+l)/2;
ll x=get(root[i-1],0,m,mid);
ll y=get(root[i],0,m,mid);
if (x+h[ii][i-1]<y) l=mid;
else r=mid;
}
// cout << get(root[1],0,m,3) << endl;
if (l!=-1){
cop(root[i],root[i-1],0,m,0,l+1);
// cout << get(root[1],0,m,3) << " f " << l+1 << endl;
root[i]=add(root[i],0,m,0,l+1,h[ii][i-1]);
// if (i==2) cout << "ROO " << get(root[2],0,m,2) << " " << l << endl;
}
// if (get(root[2],0,m,2)>0) cout << i << " sh " << endl;
}
for (int i=m-2;i>-1;i--){
ll l=-1,r=m;
while(r-l>1){
ll mid=(r+l)/2;
ll x=get(root[i+1],0,m,mid);
ll y=get(root[i],0,m,mid);
if (x+h[ii][i]<y){
r=mid;
}
else l=mid;
}
if (r!=m){
cop(root[i],root[i+1],0,m,r,m);
root[i]=add(root[i],0,m,r,m,h[ii][i]);
}
}
// for (int i=0;i<m;i++){
// cout << get(root[1],0,m,i) << " ";
// }
// cout << endl;
if (ii!=RR-1){
for (int i=0;i<m;i++){
// if (i==1) cout << v[ii][i] << endl;
root[i]=add(root[i],0,m,0,m,v[ii][i]);
// cout << v[ii][i] << endl;
// if (i==2) cout << v[ii][i] << " fjn " << get(root[i],0,m,2) << endl;
}
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
n=R;
m=C;
for (int i=0;i<5000;i++) for (int j=0;j<200;j++) h[i][j]=H[i][j],v[i][j]=V[i][j];
solve(n,m);
return ;
}
void changeH(int P, int Q, int W) {
/* ... */
h[P][Q]=W;
solve(n,m);
// cout << "SHASH" << endl;
}
void changeV(int P, int Q, int W) {
/* ... */
v[P][Q]=W;
solve(n,m);
}
int escape(int V1, int V2) {
ll ans=get(root[V2],0,m,V1);
return ans;
}
/*
int H[5000][200],V[5000][200];
int32_t main(){
cin >> n >> m;
for (int i=0;i<n;i++){
for (int j=0;j<m-1;j++) cin >> H[i][j];
}
for (int i=0;i<n-1;i++){
for (int j=0;j<m;j++) cin >> V[i][j];
}
intit(n,m,H,V);
ll q;
cin >> q;
while(q--){
ll ty;
cin >> ty;
if (ty==3){
ll x,y;
cin >> x >> y;
cout << escape(x,y) << " ans " << endl;
}
if (ty==2){
ll x,y,w;
cin >> x >> y >> w;
changeV(x,y,w);
}
if (ty==1){
ll x,y,w;
cin >> x >> y >> w;
changeH(x,y,w);
}
}
}
3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1
*/
