#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
using namespace std;
class intervalac2d{
ll n1, n2;
vec<vec<ll>> in;
vec<ll> l, l2, r, r2;
ll gcd(ll a, ll b){
if(a > b) swap(a, b);
while(a){
b %= a;
swap(a, b);
}
return b;
}
public:
void postav(ll v1, ll v2){
n1 = 1;
while(n1 < v1) n1 *= 2;
n2 = 1;
while(n2 < v2) n2 *= 2;
in.resize(2*n1, vec<ll>(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(ll i = n1-1; i >= 1; i--){
l[i] = l[2*i];
r[i] = r[2*i+1];
}
for(ll i = n2-1; i >= 1; i--){
l2[i] = l2[2*i];
r2[i] = r2[2*i+1];
}
return;
}
void zmen(ll a, ll b, ll x){
a += n1; b += n2;
in[a][b] = x;
for(ll i = a/2; i >= 1; i/=2){
in[i][b] = gcd(in[2*i][b], in[2*i + 1][b]);
}
for(ll i = a; i >= 1; i/=2){
for(ll j = b/2; j >= 1; j/=2){
in[i][j] = gcd(in[i][2*j], in[i][2*j + 1]);
}
}
return;
}
ll daj_suc_stlpce(ll a, ll b, ll c, ll 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));
}
ll daj_suc(ll a, ll b, ll c, ll d, ll 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 r1, int c1){
ll r = r1, c = c1;
seg.postav(r, c);
return;
}
void update(int a1, int b1, ll k){
ll a = a1, b = b1;
seg.zmen(a, b, k);
return;
}
ll calculate(int a1, int b1, int c1, int d1){
ll a = a1, b = b1, c = c1, d = d1;
return seg.daj_suc(min(a, c), max(a, c), min(b, d), max(b, d));
}
