#include "game.h"
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <deque>
typedef long long ll;
using namespace std;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct SEG2{
int s, e;
int l=-1, r=-1;
ll gcd = 0;
};
vector<SEG2> s2;
struct SEG1{
int s, e;
int l, r;
vector<SEG2> seg2;
};
vector<SEG1> seg1;
int r, c;
void init(int R, int C) {
r = R; c = C;
seg1.push_back({0, R-1, -1, -1, s2});
}
int qq;
ll k;
void update2(int x, int y){
//seg1[x].seg2[y].gcd = gcd2(seg1[x].seg2[y].gcd, K);
if(seg1[x].seg2[y].s==seg1[x].seg2[y].e){
seg1[x].seg2[y].gcd = k;
return;
}
if(qq<=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2){
if(seg1[x].seg2[y].l==-1){
seg1[x].seg2[y].l = seg1[x].seg2.size();
SEG2 tmp; tmp.s=seg1[x].seg2[y].s; tmp.e=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2; tmp.l=-1;tmp.r=-1;tmp.gcd=0;
seg1[x].seg2.push_back(tmp);
}
update2(x, seg1[x].seg2[y].l);
if(seg1[x].seg2[y].r==-1) seg1[x].seg2[y].gcd = seg1[x].seg2[seg1[x].seg2[y].l].gcd;
else seg1[x].seg2[y].gcd = gcd2(seg1[x].seg2[seg1[x].seg2[y].l].gcd, seg1[x].seg2[seg1[x].seg2[y].r].gcd);
}else{
if(seg1[x].seg2[y].r==-1){
seg1[x].seg2[y].r = seg1[x].seg2.size();
SEG2 tmp; tmp.s=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2+1; tmp.e=seg1[x].seg2[y].e; tmp.l=-1;tmp.r=-1;tmp.gcd=0;
seg1[x].seg2.push_back(tmp);
}
update2(x, seg1[x].seg2[y].r);
if(seg1[x].seg2[y].l==-1) seg1[x].seg2[y].gcd = seg1[x].seg2[seg1[x].seg2[y].r].gcd;
else seg1[x].seg2[y].gcd = gcd2(seg1[x].seg2[seg1[x].seg2[y].l].gcd, seg1[x].seg2[seg1[x].seg2[y].r].gcd);
}
}
int pp;
ll findg(int x, int y){
if(y==-1) return 0;
if(seg1[x].seg2[y].s==seg1[x].seg2[y].e) return seg1[x].seg2[y].gcd;
if(qq<=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2) return findg(x, seg1[x].seg2[y].l);
else return findg(x, seg1[x].seg2[y].r);
}
void update1(int x){
if(seg1[x].seg2.empty()){
SEG2 tmp;tmp.s=0;tmp.e=c-1;tmp.l=-1;tmp.r=-1;tmp.gcd=0;
seg1[x].seg2.push_back(tmp);
}
if(seg1[x].s==seg1[x].e){
update2(x, 0); return;
}
if(pp<=(seg1[x].s+seg1[x].e)/2){
if(seg1[x].l==-1){
seg1[x].l = seg1.size();
seg1.push_back({seg1[x].s, (seg1[x].s+seg1[x].e)/2, -1, -1, s2});
}
update1(seg1[x].l);
if(seg1[x].r!=-1 && !seg1[seg1[x].r].seg2.empty()) k = gcd2(k, findg(seg1[x].r, 0));
}else{
if(seg1[x].r==-1){
seg1[x].r = seg1.size();
seg1.push_back({(seg1[x].s+seg1[x].e)/2+1, seg1[x].e, -1, -1, s2});
}
update1(seg1[x].r);
if(seg1[x].l!=-1 && !seg1[seg1[x].l].seg2.empty()) k = gcd2(k, findg(seg1[x].l, 0));
}
update2(x, 0);
}
void update(int P, int Q, long long K) {
pp = P; qq = Q; k = K;
update1(0);
}
int p, q, u, v;
ll calc2(int x, int y){
if(y==-1) return 0;
if(seg1[x].seg2[y].s > v || seg1[x].seg2[y].e < q) return 0;
if(q <= seg1[x].seg2[y].s && seg1[x].seg2[y].e <= v) return seg1[x].seg2[y].gcd;
return gcd2(calc2(x, seg1[x].seg2[y].l), calc2(x, seg1[x].seg2[y].r));
}
ll calc1(int x){
if(x==-1) return 0;
if(seg1[x].s>u || seg1[x].e<p) return 0;
if(p <= seg1[x].s && seg1[x].e <= u){
if(seg1[x].seg2.empty()) return 0;
else{
return calc2(x, 0);
}
}
return gcd2(calc1(seg1[x].l), calc1(seg1[x].r));
}
long long calculate(int P, int Q, int U, int V) {
p = P; q = Q;
u = U; v = V;
return calc1(0);
}
