#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int h[5050][222];
int v[5050][222];
struct Node{
Node *l, *r;
int data[222][222];
Node() : l(0), r(0) {
memset(data, 0, sizeof data);
}
};
void merge(int a[222][222], int b[222][222], int c[222][222]){ //a = b + c
int K[222][222] = {0};
for(int d=1-m; d<m; d++){
for(int i=1; i<=m; i++){
int j = i + d;
if(j < 1 || j > m) continue;
a[i][j] = 1e9+7;
int l = K[i][j-1] ? K[i][j-1] : 1;
int r = K[i+1][j] ? K[i+1][j] : m;
for(int k=l; k<=r; k++){
if(a[i][j] > b[i][k] + c[k][j]) a[i][j] = b[i][k] + c[k][j], K[i][j] = k;
}
}
}
}
void small(int data[222][222], int s, int e){
for(int i=1; i<=m; i++) for(int j=1; j<=m; j++) data[i][j] = 1e9+7;
for(int i=1; i<=m; i++) data[i][i] = 0;
int sum[222] = {0}, a[222][222] = {0}, b[222][222] = {0};
for(int i=s; i<=e+1; i++){
for(int j=1; j<=m; j++){
for(int k=1; k<=m; k++){
a[j][k] = data[j][k];
if(i != s) a[j][k] += v[i-1][k];
}
}
for(int j=2; j<=m; j++) sum[j] = sum[j-1] + h[i][j-1];
for(int j=1; j<=m; j++){
for(int k=j; k<=m; k++){
b[j][k] = b[k][j] = sum[k] - sum[j];
}
}
merge(data, a, b);
}
}
Node* build(int s, int e){
Node *ret = new Node();
if(e-s < 15){
small(ret->data, s, e);
return ret;
}
int m = s + e >> 1;
ret->l = build(s, m);
ret->r = build(m+1, e);
merge(ret->data, ret->l->data, ret->r->data);
return ret;
}
void update(Node *node, int s, int e, int l, int r){
if(r < s || e < l) return;
if(e-s < 15){
small(node->data, s, e);
return;
}
int m = s + e >> 1;
update(node->l, s, m, l, r);
update(node->r, m+1, e, l, r);
merge(node->data, node->l->data, node->r->data);
}
Node *root;
void init(int R, int C, int H[5000][200], int V[5000][200]){
n = R; m = C;
for(int i=1; i<=n; i++) for(int j=1; j<m; j++) h[i][j] = H[i-1][j-1];
for(int i=1; i<n; i++) for(int j=1; j<=m; j++) v[i][j] = V[i-1][j-1];
root = build(1, n-1);
}
void changeH(int i, int j, int k){
i++; j++; h[i][j] = k;
update(root, 1, n-1, i-1, i);
}
void changeV(int i, int j, int k){
i++; j++; v[i][j] = k;
update(root, 1, n-1, i, i);
}
int escape(int i, int j){
i++; j++;
return root->data[i][j];
}
