#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p" = {"<<p.first<<", "<<p.second<<"}\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
const int SEGSZ=20000000, SEGSZ2=1000000;
struct Node{
ll val=0;
Node *L=NULL, *R=NULL;
};
ll ans;
Node* Set(Node *v, int tl, int tr, int pos, ll val){
// debug2(tl, tr)
// debug(v)
if (!v){
// debug("shit")
// new Node;
v=new Node;
}
// debug("built new node")
if (tr-tl==1){
// debug("shit")
(v->val)=val;
// debug("did shit")
return v;
}
// debug("going down")
int mid=(tl+tr)>>1;
if (pos<mid) (v->L)=Set((v->L), tl, mid, pos, val);
else (v->R)=Set((v->R), mid, tr, pos, val);
// debug("update?")
(v->val)=gcd2(((v->L)?v->L->val:0), ((v->R)?v->R->val:0));
// debug("updated")
return v;
}
void Get(Node *v, int tl, int tr, int l, int r, ll &ans){
if (r<=tl || tr<=l || !v) return ;
if (l<=tl && tr<=r){
ans=gcd2(ans, v->val); // overall log(10^18) for single query of problem
return ;
}
int mid=(tl+tr)>>1;
Get(v->L, tl, mid, l, r, ans);
Get(v->R, mid, tr, l, r, ans);
}
int n, m, root;
int L2[SEGSZ2], R2[SEGSZ2], ts2;
Node *seg2[SEGSZ2];
int Set2(int id, int tl, int tr, int x, int y, ll val){
if (!id) id=++ts2;
// cerr<<"update "<<val<<" in "<<tl<<" "<<tr<<"\n";
if (tr-tl==1) {
// debug("Set")
seg2[id]=Set(seg2[id], 0, m, y, val);
// debug("Seted")
return id;
}
int mid=(tl+tr)>>1;
if (x<mid) L2[id]=Set2(L2[id], tl, mid, x, y, val);
else R2[id]=Set2(R2[id], mid, tr, x, y, val);
// debug2(L2[id], R2[id])
// debug2(seg[seg2[L2[id]]], seg[seg2[R2[id]]])
ll res=0;
Get(seg2[L2[id]], 0, m, y, y+1, res);
Get(seg2[R2[id]], 0, m, y, y+1, res);
// debug(res)
seg2[id]=Set(seg2[id], 0, m, y, res);
return id;
}
void Get2(int id, int tl, int tr, int l1, int l2, int r1, int r2){
if (r1<=tl || tr<=l1 || !id) return ;
if (l1<=tl && tr<=r1){
// debug2(tl, tr)
Get(seg2[id], 0, m, l2, r2, ans);
return ;
}
int mid=(tl+tr)>>1;
Get2(L2[id], tl, mid, l1, l2, r1, r2);
Get2(R2[id], mid, tr, l1, l2, r1, r2);
}
void init(int nn, int mm) {
n=nn;
m=mm;
}
void update(int P, int Q, ll K){
// debug("update")
root=Set2(root, 0, n, P, Q, K);
// debug("done")
}
ll calculate(int P, int Q, int U, int V) {
ans=0;
Get2(root, 0, n, P, Q, U+1, V+1);
return ans;
}
/*
3 3 4
2 0 1 2 2
1 1 0 13
1 2 2 1
2 0 0 2 2
*/
