#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
mt19937 rng(1);
ll r, c;
struct treap
{
struct node
{
ll sz, key, vl, g;
pair<ll, ll> idx;
node *l, *r;
node(ll vl, pair<ll, ll> idx): sz(1), key(rng()), vl(vl), g(vl), idx(idx), l(0), r(0){}
};
typedef node* pnode;
pnode rt=0;
ll size(pnode x)
{
return x?x->sz:0;
}
ll g(pnode x)
{
return x?x->g:0;
}
void update(pnode x)
{
if (!x) return;
x->sz=size(x->l)+size(x->r)+1;
x->g=gcd(gcd(g(x->l), g(x->r)), x->vl);
}
void merge(pnode l, pnode r, pnode &k)
{
if (!l) return k=r, void();
if (!r) return k=l, void();
if (l->key>=r->key) merge(l->r, r, l->r), k=l;
else merge(l, r->l, r->l), k=r;
update(k);
}
void split(pnode &l, pnode &r, pnode k, pair<ll, ll> idx)
{
if (!k) return l=r=0, void();
if (k->idx>=idx) split(l, k->l, k->l, idx), r=k;
else split(k->r, r, k->r, idx), l=k;
update(l);
update(r);
}
void split2(pnode &l, pnode &r, pnode k, ll key)
{
if (!k) return l=r=0, void();
if (size(k->l)+1<=key) split2(k->r, r, k->r, key-(1+size(k->l))), l=k;
else split2(l, k->l, k->l, key), r=k;
update(l);
update(r);
}
void add(pair<ll, ll> idx, ll vl)
{
pnode p1, p2, p3;
split(p1, p2, rt, idx);
if (!p2) return merge(p1, new node(vl, idx), rt), void();
split2(p2, p3, p2, 1);
if (p2->idx==idx) return p2->vl=vl, merge(p2, p3, p2), merge(p1, p2, rt), void();
merge(p2, p3, p2);
merge(new node(vl, idx), p2, p2);
merge(p1, p2, rt);
}
ll query(ll l, ll r)
{
pnode p1, p2, p3;
split(p1, p2, rt, {l, -1});
split(p2, p3, p2, {r+1, -1});
ll res=p2?p2->g:0;
merge(p2, p3, p2);
merge(p1, p2, rt);
return res;
}
void traverse(pnode x)
{
if (!x) return;
traverse(x->l);
cout<<x->idx.first<<' '<<x->key<<' '<<x->g<<'\n';
traverse(x->r);
}
treap(): rt(0){}
};
typedef treap* ptreap;
vector<ptreap> v;
void init(int R, int C) {
r=R, c=C;
for (int i=0; i<R; i++) v.push_back(new treap());
}
void update(int P, int Q, long long K) {
//cout<<"P "<<P<<' '<<Q<<' '<<K<<'\n';
v[P]->add({Q, P}, K);
//cout<<"after update "<<v[P]->rt->g<<'\n';
}
long long calculate(int P, int Q, int U, int V) {
ll res=0;
//cout<<"q "<<P<<' '<<Q<<' '<<U<<' '<<V<<'\n';
//v[0]->traverse(v[0]->rt);
//cout<<"query row "<<i<<":"<<v[i]->query(Q, V)<<'\n',
for (int i=P; i<=U; i++) res=gcd(res, v[i]->query(Q, V));
return res;
}
// g++ grader.cpp game3.cpp -o a
