#include<bits/stdc++.h>
#include <random>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
mt19937 mt(time(nullptr));
struct Treap{
struct Node{
Node *left, *right;
ll x, y, gcd, fgcd;
Node(ll _x, ll _gcd){
left=right=nullptr;
x=_x; gcd=fgcd=_gcd;
y=mt();
}
Node(ll _x, ll _y, ll _gcd){
left=right=NULL;
x=_x; y=_y; gcd=fgcd=_gcd;
}
};
Node * root;
Treap(){
root=new Node(-1, 2e18, 0);
}
void upd(Node * t){
if (!t) return;
t->fgcd=t->gcd;
if (t->left) t->fgcd=__gcd(t->left->fgcd, t->fgcd);
if (t->right) t->fgcd=__gcd(t->right->fgcd, t->fgcd);
}
void split(Node *par, Node*&wl, Node*&wr, ll x){
if (!par){
wl=wr=nullptr;
}else if (par->x<=x){
split(par->right, par->right, wr, x); wl=par;
}else{
split(par->left, wl, par->left, x); wr=par;
}
upd(wl); upd(wr);
}
void merge(Node *& npar, Node *l, Node *r){
if (!l or !r){
npar=l?l:r;
}else if (l->y>r->y){
merge(l->right, l->right, r); npar=l;
}else{
merge(r->left, l, r->left); npar=r;
}
upd(npar);
}
void insert(Node *& cur, Node * item){
if (!cur){
cur=item;
}else if (cur->y>=item->y){
insert(cur->x<=item->x?cur->right:cur->left, item);
}else{
split(cur, item->left, item->right, item->x); cur=item;
}
upd(cur);
}
ll query_range(Node *& cur, ll l, ll r){
Node * t1, * t2, * t3;
split(cur, t1, t2, l-1);
split(t2, t2, t3, r);
ll res=t2?t2->fgcd:0;
merge(cur, t1, t2);
merge(cur, cur, t3);
return res;
}
void update(Node * cur, ll x, ll newval){
if (!cur){
insert(root, new Node(x, newval));
return;
}else if (cur->x==x){
cur->gcd=newval;
}else if (cur->x<x){
update(cur->right, x, newval);
}else{
update(cur->left, x, newval);
}
upd(cur);
}
void update(ll x, ll newval){
update(root, x, newval);
}
void insert(ll x, ll val){
insert(root, new Node(x, val));
}
ll query(ll l, ll r){
return query_range(root, l, r);
}
};
// struct SegTree1D{
// struct Node{
// ll left, right, val;
// Node(){
// left=right=-1;
// val=0;
// }
// };
// vector<Node> nodes;
// ll add_node(){
// nodes.push_back(Node());
// return nodes.size()-1;
// }
// map<int, ll> leaves;
// int rsz;
// SegTree1D(int N){
// rsz=N;
// add_node();
// }
// void update(ll tl, ll tr, ll v, ll i, ll x){
// if (tl==tr){
// nodes[v].val=x;
// leaves[tl]=v;
// }else{
// ll tm = (tl+tr)/2;
// if (i<=tm){
// if (nodes[v].left==-1) nodes[v].left=add_node();
// update(tl, tm, nodes[v].left, i, x);
// }else{
// if (nodes[v].right==-1) nodes[v].right=add_node();
// update(tm+1, tr, nodes[v].right, i, x);
// }
// nodes[v].val=0;
// if (nodes[v].left!=-1) nodes[v].val=__gcd(nodes[nodes[v].left].val, nodes[v].val);
// if (nodes[v].right!=-1) nodes[v].val=__gcd(nodes[nodes[v].right].val, nodes[v].val);
// }
// }
// void update(ll i, ll x){
// update(0, rsz-1, 0, i, x);
// }
// ll query(ll tl, ll tr, ll v, ll l, ll r){
// if (tl==l and tr==r){
// return nodes[v].val;
// }
// else if (l>r) return 0;
// else{
// ll tm = (tl+tr)/2;
// ll res=0;
// if (nodes[v].left!=-1) res=__gcd(res, query(tl, tm, nodes[v].left, l, min(r, tm)));
// if (nodes[v].right!=-1) res=__gcd(res, query(tm+1, tr, nodes[v].right, max(l, tm+1), r));
// return res;
// }
// }
// ll query(int l, int r){
// return query(0, rsz-1, 0, l, r);
// }
// ll getval(int ind){
// if (!leaves.count(ind)) return 0;
// return nodes[leaves[ind]].val;
// }
// };
struct SegTree2D{
struct mNode{
mNode *left, *right;
Treap *val;
int csz;
mNode(int _csz){
csz=_csz;
left=right=nullptr;
val = new Treap();
}
void update(int tl, int tr, int i, int j, ll x){
if (tl==tr){
// cout << "Entered" << endl;
val->update(j, x);
// cout << "Exited"<< endl;
}else{
int tm = (tl+tr)/2;
if (i<=tm){
if (!left) left=new mNode(csz);
left->update(tl, tm, i, j, x);
}else{
if (!right) right=new mNode(csz);
right->update(tm+1, tr, i, j, x);
}
val->update(j, __gcd((left?left->val->query(j, j):0), (right?right->val->query(j, j):0)));
}
}
ll query(int li, int ri, int lj, int rj, int tl, int tr){
if (tl==li and tr==ri){
// cout << lj << "-" << rj << endl;
ll res= val->query(lj, rj);
// cout << "Success" << endl;
return res;
}else if (li>ri) return 0;
else{
ll ret=0;
int tm = (tl+tr)/2;
if (left and li<=min(ri, tm)) ret=__gcd(ret, left->query(li, min(ri, tm), lj, rj, tl, tm));
if (right and max(li, tm+1)<=ri) ret=__gcd(ret, right->query(max(li, tm+1), ri, lj, rj, tm+1, tr));
return ret;
}
}
};
mNode * root;
ll csz, rsz;
void init(int R, int C){
rsz=R; csz=C;
root = new mNode(csz);
}
void update(int i, int j, ll x){
root->update(0, rsz-1, i, j, x);
}
ll query(int li, int ri, int lj, int rj){
return root->query(li, ri, lj, rj, 0, rsz-1);
}
} DS;
void init(int R, int C) {
DS.init(R, C);
// cout << "Init" << endl;
}
void update(int P, int Q, long long K) {
// cout << "Updating " << P << "-" << Q << "-" << K << endl;
DS.update(P, Q, K);
// cout << "Updated " << P << "-" << Q << "-" << K << endl;
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
ll res= DS.query(P, U, Q, V);
// cout << "Queried" << endl;
return res;
// return 0;
}
