#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 treap{
struct node{
node*l = nullptr;
node*r = nullptr;
ll key, hod, sum;
ll priority = rand();
node(ll val1, ll val2){
key = val1;
sum = val2;
hod = val2;
}
};
typedef node* pnode;
pnode root = nullptr;
ll get_sum(pnode s){
if(!s) return 0;
return s->sum;
}
void update(pnode &s){
if(!s) return;
s->sum = nsd(nsd(get_sum(s->l), get_sum(s->r)), s->hod);
return;
}
void pridaj(pnode x, pnode &t){
if(!t) {
t = x;
return;
}
if(x->priority > t->priority){
split(t, x->l, x->r, x->key);
update(x);
t = x;
return;
}
x->key > t->key ? pridaj(x, t->r) : pridaj(x, t->l);
update(t);
return;
}
void erase(ll x, pnode &t){
if(!t) return;
if(t->key == x){
merge(t, t->l, t->r);
return;
}
x > t->key ? erase(x, t->r) : erase(x, t->l);
update(t);
return;
}
void merge(pnode &t, pnode l, pnode r){
if(!l || !r) {
t = l ? l : r;
return;
}
if(l->priority > r->priority){
merge(l->r, l->r, r);
t = l;
}
else{
merge(r->l, l, r->l);
t = r;
}
update(t);
return;
}
void split(pnode t, pnode &l, pnode &r, ll key){
if(!t) {
l = r = nullptr;
return;
}
if(t->key > key){
split(t->l, l, t->l, key);
r = t;
}
else{
split(t->r, t->r, r, key);
l = t;
}
update(t);
return;
}
public:
void pridaj_p(ll x, ll h){
erase(x, root);
pridaj(new node(x, h), root);
}
ll sum(ll a, ll b){
pnode l, r;
l = r = nullptr;
split(root, root, r, a-1);
split(r, l, r, b);
ll odp = get_sum(l);
merge(root, root, l);
merge(root, root, r);
return odp;
}
};
class intervalac2d{
ll n;
ll m;
struct node{
treap in;
node* l = nullptr;
node* r = nullptr;
};
typedef node* pnode;
pnode root = nullptr;
ll get_range(pnode s, ll a, ll b){
if(!s) return (ll)0;
return s->in.sum(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;
if(l == r){
s->in.pridaj_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.pridaj_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) return (ll)0;
if(a <= l && r <= b) {
return s->in.sum(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));
}
