#include "game.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define NEK 1000000000
#define ll long long
#define vec vector
#define For(i, n) for(int i = 0; i < n; i++)
#define pii pair<int, int>
#define ff first
#define ss second
#define int ll
using namespace std;
class intervalac2d{
int n1, n2;
vec<vec<int>> in;
vec<int> l, l2, r, r2;
int gcd(int a, int b){
if(a > b) swap(a, b);
while(!a){
b %= a;
swap(a, b);
}
return b;
}
public:
void postav(int v1, int v2){
n1 = 1;
while(n1 < v1) n1 *= 2;
n2 = 1;
while(n2 < v2) n2 *= 2;
in.resize(2*n1, vec<int>(2*n2, 0));
l.resize(2*n1);
r.resize(2*n1);
l2.resize(2*n2);
r2.resize(2*n2);
For(i, n1){
l[i+n1] = r[i+n1] = i;
}
For(i, n2){
l2[i+n2] = r2[i+n2] = i;
}
for(int i = n1-1; i >= 1; i--){
l[i] = l[2*i];
r[i] = r[2*i+1];
}
for(int i = n2-1; i >= 1; i--){
l2[i] = l2[2*i];
r2[i] = r2[2*i+1];
}
return;
}
void zmen(int a, int b, int x){
a += n1; b += n2;
in[a][b] = x;
for(int i = a/2; i >= 1; i/=2){
in[i][b] = gcd(in[2*i][b] + in[2*i + 1][b]);
}
for(int i = a; i >= 1; i/=2){
for(int j = b/2; j >= 1; j/=2){
in[i][j] = gcd(in[i][2*j] + in[i][2*j + 1]);
}
}
return;
}
int daj_suc_stlpce(int a, int b, int c, int s = 1){
if(a > r2[s] || b < l2[s]) return (ll)0;
if(a <= l2[s] && r2[s] <= b) return in[c][s];
return gcd(daj_suc_stlpce(a, b, c, 2*s) + daj_suc_stlpce(a, b, c, 2*s + 1));
}
int daj_suc(int a, int b, int c, int d, int s = 1){
if(a > r[s] || b < l[s]) return (ll)0;
if(a <= l[s] && r[s] <= b) return daj_suc_stlpce(c, d, s);
return gcd(daj_suc(a, b, c, d, 2*s), daj_suc(a, b, c, d, 2*s + 1));
}
};
intervalac2d seg;
void init(int r, int c){
seg.postav(r, c);
return;
}
void update(int a, int b, ll k){
seg.zmen(a, b, k);
return;
}
int calculate(int a, int b, int c, int d){
return seg.daj_suc(min(a, c), max(a, c), min(b, d), max(b, d));
}
