#include<bits/stdc++.h>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
struct SegTree1D{
struct Node{
map<ll, Node*> con;
ll gcd;
Node(){
gcd=0;
}
void update(ll tl, ll tr, ll i, ll x, map<ll, Node*> &leaves){
if (tl==tr){
gcd=x;
leaves[tl]=this;
}else{
ll tm = (tl+tr)/2;
if (i<=tm) {
if (!con.count(0)) con[0]=new Node();
con[0]->update(tl, tm, i, x, leaves);
}else{
if (!con.count(1)) con[1]=new Node();
con[1]->update(tm+1, tr, i, x, leaves);
}
gcd=0;
if(con.count(0)) gcd=__gcd(con[0]->gcd, gcd);
if (con.count(1)) gcd=__gcd(con[1]->gcd, gcd);
}
}
ll query(ll tl, ll tr, ll l, ll r){
if (tl==l and tr==r){
return gcd;
}else if (l>r) return 0;
else{
ll tm = (tl+tr)/2;
ll ret=0;
if (con.count(0) and l<=min(r, tm)) ret=__gcd(ret, con[0]->query(tl, tm, l, min(r, tm)));
if (con.count(1) and max(l, tm+1)<=r) ret=__gcd(ret, con[1]->query(tm+1, tr, max(l, tm+1), r));
return ret;
}
}
};
map<ll, Node*> leaves;
Node * root;
ll rsz;
SegTree1D(ll N){
rsz=N;
root=new Node();
}
void update(ll i, ll x){
root->update(0, rsz-1, i, x, leaves);
}
ll query(ll l, ll r){
return root->query(0, rsz-1, l, r);
}
ll getval(ll ind){
if (!leaves.count(ind)) return 0;
return leaves[ind]->gcd;
}
};
struct SegTree2D{
struct mNode{
map<ll, mNode*> con;
SegTree1D *val;
ll csz;
mNode(ll _csz){
csz=_csz;
val = new SegTree1D(csz);
}
void update(ll tl, ll tr, ll i, ll j, ll x){
if (tl==tr){
val->update(j, x);
}else{
ll tm = (tl+tr)/2;
if (i<=tm){
if (!con.count(0)) con[0]=new mNode(csz);
con[0]->update(tl, tm, i, j, x);
}else{
if (!con.count(1)) con[1]=new mNode(csz);
con[1]->update(tm+1, tr, i, j, x);
}
val->update(j, __gcd((con.count(0)?con[0]->val->getval(j):0), (con.count(1)?con[1]->val->getval(j):0)));
}
}
ll query(ll li, ll ri, ll lj, ll rj, ll tl, ll tr){
if (tl==li and tr==ri){
return val->query(lj, rj);
}else if (li>ri) return 0;
else{
ll ret=0;
ll tm = (tl+tr)/2;
if (con.count(0) and li<=min(ri, tm)) ret=__gcd(ret, con[0]->query(li, min(ri, tm), lj, rj, tl, tm));
if (con.count(1) and max(li, tm+1)<=ri) ret=__gcd(ret, con[1]->query(max(li, tm+1), ri, lj, rj, tm+1, tr));
return ret;
}
}
};
mNode * root;
ll csz, rsz;
void init(ll R, ll C){
rsz=R; csz=C;
root = new mNode(csz);
}
void update(ll i, ll j, ll x){
root->update(0, rsz-1, i, j, x);
}
ll query(ll li, ll ri, ll lj, ll rj){
return root->query(li, ri, lj, rj, 0, rsz-1);
}
} DS;
void init(int R, int C) {
DS.init(R, C);
}
void update(int P, int Q, long long K) {
DS.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
return DS.query(P, U, Q, V);
}
