#include<bits/stdc++.h>
#include "game.h"
using namespace std;
#define tm (tl+tr >> 1)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
inline ll gcd(ll u, ll v) {
ll r;
while (v != 0) { r = u % v; u = v; v = r; }
return u;
}
struct node{
ll x;
int tl, tr;
struct node *l, *r, *to_y;
node() { x = 0; l = r = to_y = NULL; }
node* nw(int l, int r){
node* p = (node*) malloc(sizeof(node));
p -> tl = l; p -> tr = r;
return p;
}
ll qry_y(int ly, int ry) {
if(ly > tr || ry < tl) return 0;
if (ly <= tl && tr <= ry) return x;
return gcd(l ? l->qry_y(ly,ry) : 0 , r ? r->qry_y(ly,ry) : 0);
}
ll qry_x(int lx, int rx, int ly, int ry) {
if(lx > tr || rx < tl) return 0;
if (lx <= tl && tr <= rx) return to_y ? to_y->qry_y(ly,ry) : 0;
return gcd(l ? l->qry_x(lx,rx,ly,ry) : 0 , r ? r->qry_x(lx,rx,ly,ry) : 0);
}
void up_y(int py, ll val){
if(tl == tr){ x = val; return; }
if(py > tm) { if(r == NULL) r = nw(tm+1,tr); r -> up_y(py,val); }
else { if(l == NULL) l = nw(tl,tm); l -> up_y(py,val); }
x = gcd(l ? l->x : 0 , r ? r->x : 0);
}
void up_x(int px, int py, ll val){
if(tl < tr){
if(px > tm) { if(r == NULL) r = nw(tm+1,tr); r -> up_x(px,py,val); }
else { if(l == NULL) l = nw(tl,tm); l -> up_x(px,py,val); }
val = gcd(l ? l->to_y->qry_y(py,py) : 0 , r ? r->to_y->qry_y(py,py) : 0);
}
if(to_y == NULL) to_y = nw(0,mod); to_y -> up_y(py,val);
}
} root;
void update(int x, int y, ll val){
root.up_x(x,y,val);
}
ll calculate(int lx, int ly, int rx, int ry){
return root.qry_x(lx,rx,ly,ry);
}
void init(int a, int b) { root.tl = 0; root.tr = mod; }
