// And you curse yourself for things you never done
#include<bits/stdc++.h>
#include "game.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAX = (3e5) * 70;
int N, M;
int L[MAX], R[MAX];
ll g[MAX];
int C;
inline int NEW(){
return ++C;
}
void _put(int id, int pos, ll x, int l = 0, int r = M){
if(r-l == 1){
g[id] = x;
return;
}
int mid = (l+r) >> 1;
if(pos < mid){
if(!L[id])
L[id] = NEW();
_put(L[id], pos, x, l, mid);
}
else{
if(!R[id])
R[id] = NEW();
_put(R[id], pos, x, mid, r);
}
g[id] = __gcd(L[id] ? g[L[id]] : 0, R[id] ? g[R[id]] : 0);
}
ll _ask(int id, int f, int s, int l = 0, int r = M){
if(r <= f || s <= l)
return 0;
if(f <= l && r <= s)
return g[id];
int mid = (l+r) >> 1;
return __gcd(L[id] ? _ask(L[id], f, s, l, mid) : 0, R[id] ? _ask(R[id], f, s, mid, r) : 0);
}
struct node2{
int g = 0;
node2 *L = 0, *R = 0;
void put(int posx, int posy, ll x, int l = 0, int r = N){
ll num = x;
if(r-l > 1){
int mid = (l+r) >> 1;
if(posx < mid){
if(!L)
L = new node2();
L->put(posx, posy, x, l, mid);
}
else{
if(!R)
R = new node2();
R->put(posx, posy, x, mid, r);
}
num = __gcd(L ? _ask(L->g, posy, posy+1) : 0, R ? _ask(R->g, posy, posy+1) : 0);
}
if(!g)
g = NEW();
_put(g, posy, num);
}
ll ask(int f, int s, int ff, int ss, int l = 0, int r = N){
if(r <= f || s <= l)
return 0;
if(f <= l && r <= s)
return g ? _ask(g, ff, ss) : 0;
int mid = (l+r) >> 1;
return __gcd(L ? L->ask(f, s, ff, ss, l, mid) : 0, R ? R->ask(f, s, ff, ss, mid, r) : 0);
}
};
node2* root;
void init(int N, int M){
::N = N, ::M = M;
root = new node2();
}
void update(int x, int y, ll w){
root->put(x, y, w);
}
ll calculate(int x, int y, int xx, int yy){
return root->ask(x, ++xx, y, ++yy);
}
