#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll gcd__(ll a, ll b) {
return b?gcd__(b, a%b):a;
}
int p, q;
struct Node {
int l, r; ll val;
Node() {l=r=-1, val=0;}
}buf[15000000];
const int S=1<<30;
class seg2d {
public:
seg2d() { root=q++; }
void update(int x, int y, ll v) { update(root, 0, S-1, x, y, v); }
ll query(int s, int e, int l, int r) { return query(root, 0, S-1, s, e, l, r); }
private:
class seg1d {
public:
int root, l, r;
seg1d() { root=p++; l=r=-1; }
void update(int k, ll v) { update(root, 0, S-1, k, v); }
void merge(int k, int v1, int v2) {merge(root, v1, v2, 0, S-1, k);}
ll query(int l, int r) { return query(root, 0, S-1, l, r); }
private:
void update(int curr, int s, int e, int k, ll v) {
if(s==e) {
buf[curr].val=v; return;
}
int m=(s+e)/2;
if(k<=m) {
if(buf[curr].l<0) buf[curr].l=p++;
update(buf[curr].l, s, m, k, v);
if(buf[curr].r>=0) buf[curr].val=gcd__(buf[buf[curr].l].val, buf[buf[curr].r].val);
else buf[curr].val=buf[buf[curr].l].val;
}
else {
if(buf[curr].r<0) buf[curr].r=p++;
update(buf[curr].r, m+1, e, k, v);
if(buf[curr].l>=0) buf[curr].val=gcd__(buf[buf[curr].l].val, buf[buf[curr].r].val);
else buf[curr].val=buf[buf[curr].r].val;
}
}
void merge(int curr, int curr1, int curr2, int s, int e, int k) {
buf[curr].val=gcd__((curr1>=0)?buf[curr1].val:0, (curr2>=0)?buf[curr2].val:0);
if(s==e) return;
int m=(s+e)/2;
if(k<=m) {
if(buf[curr].l<0) buf[curr].l=p++;
merge(buf[curr].l, (curr1>=0)?buf[curr1].l:-1, (curr2>=0)?buf[curr2].l:-1, s, m, k);
}
else {
if(buf[curr].r<0) buf[curr].r=p++;
merge(buf[curr].r, (curr1>=0)?buf[curr1].r:-1, (curr2>=0)?buf[curr2].r:-1, m+1, e, k);
}
}
ll query(int curr, int s, int e, int l, int r) {
if(curr<0 || s>r || l>e) return 0;
if(l<=s && e<=r) return buf[curr].val;
int m=(s+e)/2;
return gcd__(query(buf[curr].l, s, m, l, r), query(buf[curr].r, m+1, e, l, r));
}
}tree[1000000];
int root;
void update(int curr, int s, int e, int x, int y, ll v) {
if(s==e) {
tree[curr].update(y, v);
return;
}
int m=(s+e)/2;
if(x<=m) {
if(tree[curr].l<0) tree[curr].l=q++;
update(tree[curr].l, s, m, x, y, v);
}
else {
if(tree[curr].r<0) tree[curr].r=q++;
update(tree[curr].r, m+1, e, x, y, v);
}
tree[curr].merge(y, (tree[curr].l>=0)?tree[tree[curr].l].root:-1, (tree[curr].r>=0)?tree[tree[curr].r].root:-1);
}
ll query(int curr, int s, int e, int l, int r, int ll, int rr) {
if(curr<0 || s>r || l>e) return 0;
if(l<=s && e<=r) return tree[curr].query(ll, rr);
int m=(s+e)/2;
return gcd__(query(tree[curr].l, s, m, l, r, ll, rr), query(tree[curr].r, m+1, e, l, r, ll, rr));
}
}T;
void init(int R, int C) {}
void update(int P, int Q, ll K) {
T.update(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return T.query(P, U, Q, V);
}
