#include "game.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define NEK 1000000000000
#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;
ll nsd(ll a, ll b){
if(a > b) swap(a, b);
while(a){
b %= a;
swap(a, b);
}
return b;
}
class intervalac{
ll n;
struct node{
ll sum = 0;
node* l = nullptr;
node* r = nullptr;
};
typedef node* pnode;
pnode root = nullptr;
ll get_sum(pnode s){
if(!s) return (ll)0;
return s->sum;
}
void update(pnode&s){
s->sum = nsd(get_sum(s->l), get_sum(s->r));
return;
}
void zmen(ll a, ll x, ll l, ll r, pnode& s){
if(a < l || a > r) return;
if(!s) s = new node;
if(l == r){
s->sum = x;
return;
}
int mid = (l+r)/2;
zmen(a, x, l, mid, s->l); zmen(a, x, mid+1, r, s->r);
update(s);
return;
}
ll daj(ll a, ll b, ll l, ll r, pnode&s){
if(a > r || b < l) return (ll)0;
if(!s) s = new node;
if(a <= l && r <= b) return s->sum;
ll mid = (l+r)/2;
return nsd(daj(a, b, l, mid, s->l), daj(a, b, mid+1, r, s->r));
}
public:
intervalac(int v){
n = v;
}
void zmen_p(ll a, ll x){
zmen(a, x, 0, n-1, root);
}
ll daj_p(ll a, ll b){
return daj(a, b, 0, n-1, root);
}
};
class intervalac2d{
ll n;
ll m;
struct node{
intervalac in;
node* l = nullptr;
node* r = nullptr;
node(ll m) : in(m) {}
};
typedef node* pnode;
pnode root = nullptr;
int get_range(pnode s, ll a, ll b){
if(!s) return (ll)0;
return s->in.daj_p(a, b);
}
void zmen(ll a, ll b, ll x, ll l, ll r, pnode& s){
if(a < l || a > r) return;
if(!s) s = new node(m);
if(l == r){
s->in.zmen_p(b, x);
return;
}
ll mid = (l+r)/2;
zmen(a, b, x, l, mid, s->l); zmen(a, b, x, mid+1, r, s->r);
ll val = nsd(get_range(s->l, b, b), get_range(s->r, b, b));
s->in.zmen_p(b, val);
return;
}
ll daj(ll a, ll b, ll c, ll d, ll l, ll r, pnode&s){
if(a > r || b < l) return (ll)0;
if(!s) s = new node(m);
if(a <= l && r <= b) {
return s->in.daj_p(c, d);
}
ll mid = (l+r)/2;
return nsd(daj(a, b, c, d, l, mid, s->l), daj(a, b, c, d, mid+1, r, s->r));
}
public:
void postav(ll v1, ll v2){
n = v1, m = v2;
}
void zmen_p(ll a, ll b, ll x){
zmen(a, b, x, 0, n-1, root);
}
ll daj_p(ll a, ll b, ll c, ll d){
return daj(a, b, c, d, 0, n-1, root);
}
};
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_p(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_p(min(a, c), max(a, c), min(b, d), max(b, d));
}
