#include<iostream>
#include "game.h"
using namespace std;
/// struct
struct Tnode
{
long long val;
Tnode *l, *r;
Tnode()
{
val = 0;
l = NULL;
r = NULL;
}
};
struct Tree
{
Tnode *node;
Tree *l, *r;
Tree()
{
node = NULL;
l = NULL;
r = NULL;
}
};
Tree *root = NULL;
int r, c;
int qL, qR, ql, qr;
long long updPos, updpos, updvalue;
long long gcd(long long x, long long y)
{
while (x && y)
{
if(x > y)x %= y;
else y %= x;
}
return x + y;
}
/// query
long long query(Tnode *t, int l, int r)
{
if(qr < l && ql > r)return 0;
if(r < l)return 0;
if(t == NULL)return 0;
if(ql <= l && r <= qr)return t -> val;
int mid = (l + r)/2;
long long fhalf = query(t -> l, l, mid);
long long shalf = query(t -> r, mid+1, r);
return gcd(fhalf, shalf);
}
long long Query(Tree *t, int l, int r)
{
if(qR < l || qL > r)return 0;
if(r < l)return 0;
if(t == NULL)return 0;
if(qL <= l && r <= qR)
{
return query(t -> node, 0, c-1);
}
int mid = (l + r)/2;
long long fhalf = Query(t -> l, l, mid);
long long shalf = Query(t -> r, mid+1, r);
return gcd(fhalf, shalf);
}
/// update
long long merge0(Tnode *&t0, Tnode *&t1)
{
if(t0 == NULL && t1 == NULL)return 0;
if(t0 == NULL)return t1 -> val;
if(t1 == NULL)return t0 -> val;
return gcd(t0 -> val, t1 -> val);
}
void upd(Tnode *&t, int l, int r)
{
if(t == NULL)t = new Tnode;
if(l == r)
{
t -> val = updvalue;
return;
}
int mid = (l + r)/2;
if(updpos <= mid)upd(t -> l, l, mid);
else upd(t -> r, mid+1, r);
t -> val = merge0(t -> l, t -> r);
}
Tnode *getValue(Tree *&t)
{
if(t == NULL)return NULL;
else return t -> node;
}
long long getvalue(Tnode *&t)
{
if(t == NULL)return 0;
return t -> val;
}
void Merge(Tnode *&t, Tnode *&t0, Tnode *&t1, int l, int r)
{
if(t == NULL)t = new Tnode;
if(l == r)
{
t -> val = gcd(getvalue(t0), getvalue(t1));
return;
}
int mid = (l + r)/2;
if(updpos <= mid)
{
if(t1 != NULL)t1 = t1 -> l;
if(t0 != NULL)t0 = t0 -> l;
Merge(t ->l, t0, t1, l, mid);
}
else
{
if(t1 != NULL)t1 = t1 -> r;
if(t0 != NULL)t0 = t0 -> r;
Merge(t -> r, t0, t1, mid+1, r);
}
t -> val = gcd(getvalue(t0), getvalue(t1));
}
void Update(Tree *t, int l, int r)
{
if(t == NULL)t = new Tree();
if(l == r)
{
upd(t -> node, 0, c-1);
return;
}
int mid = (l + r)/2;
if(updPos <= mid)Update(t -> l, l, mid);
else Update(t -> r, mid+1, r);
}
void init(int R, int C) {
r = R;
c = C;
}
void update(int P, int Q, long long K)
{
updPos = P;
updpos = Q;
updvalue = K;
Update(root, 0, r-1);
}
long long calculate(int P, int Q, int U, int V)
{
qL = P;
qR = U;
ql = Q;
qr = V;
long long ans = Query(root, 0, r-1);
return ans;
}
