#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;
}
const int S=1<<30;
class seg2d {
public:
seg2d() { root=new seg1d(); }
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:
seg1d *l, *r;
seg1d() { root=new Node(); }
void update(int k, ll v) { update(root, 0, S-1, k, v); }
int query(int l, int r) { return query(root, 0, S-1, l, r); }
private:
struct Node {
Node *l, *r;
ll val;
};
Node *root;
void update(Node *curr, int s, int e, int k, ll v) {
if(s==e) {
curr->val=v; return;
}
int m=(s+e)/2;
if(k<=m) {
if(!curr->l) curr->l=new Node();
update(curr->l, s, m, k, v);
if(curr->r) curr->val=gcd__(curr->l->val, curr->r->val);
else curr->val=curr->l->val;
}
else {
if(!curr->r) curr->r=new Node();
update(curr->r, m+1, e, k, v);
if(curr->l) curr->val=gcd__(curr->l->val, curr->r->val);
else curr->val=curr->r->val;
}
}
ll query(Node *curr, int s, int e, int l, int r) {
if(!curr || s>r || l>e) return 0;
if(l<=s && e<=r) return curr->val;
int m=(s+e)/2;
return gcd__(query(curr->l, s, m, l, r), query(curr->r, m+1, e, l, r));
}
};
seg1d *root;
void update(seg1d *curr, int s, int e, int x, int y, ll v) {
curr->update(y, v);
if(s==e) return;
int m=(s+e)/2;
if(x<=m) {
if(!curr->l) curr->l=new seg1d();
update(curr->l, s, m, x, y, v);
}
else {
if(!curr->r) curr->r=new seg1d();
update(curr->r, m+1, e, x, y, v);
}
}
ll query(seg1d *curr, int s, int e, int l, int r, int ll, int rr) {
if(!curr || s>r || l>e) return 0;
if(l<=s && e<=r) {
return curr->query(ll, rr);
}
int m=(s+e)/2;
return gcd__(query(curr->l, s, m, l, r, ll, rr), query(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);
}
