#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;
const int inf = 1e9+10;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct treap{
struct node{
ii pos;
int prior;
ll val, res;
node *lef, *rig;
node(ii p = mp(0, 0), ll v = 0){
pos = p;
prior = rand();
val = v;
res = v;
lef = NULL;
rig = NULL;
}
};
// try using my own null
typedef node *pnode;
pnode root;
///this one
//map<int, ll> mym;
treap(){
root = NULL;
/// this one
//mym.clear();
}
void upd(pnode t){
if (t == NULL)
return;
t->res = t->val;
if (t->lef != NULL)
t->res = gcd2(t->res, t->lef->res);
if (t->rig != NULL)
t->res = gcd2(t->res, t->rig->res);
}
void split(pnode t, pnode &l, pnode &r, ii k){
if (t == NULL)
return void(l = r = NULL);
if (t->pos <= k)
split(t->rig, t->rig, r, k), l = t;
else
split(t->lef, l, t->lef, k), r = t;
upd(t);
}
void join(pnode &t, pnode l, pnode r){
if (l == NULL)
return void(t = r);
if (r == NULL)
return void(t = l);
if (l->prior > r->prior)
join(l->rig, l->rig, r), t = l;
else
join(r->lef, l, r->lef), t = r;
upd(t);
}
void add(ii p, ll v){
/// this one
//mym[p] = v;
//return;
pnode l = NULL, mid = NULL, r = NULL;
split(root, l, r, p);
split(l, l, mid, mp(p.fi, p.se-1));
mid = new node(p, v);
join(l, l, mid);
join(root, l, r);
}
ll ask(int a, int b){
/// this one
//ll hey = 0;
//for (auto it: mym)
// if (a <= it.first && it.first <= b)
// hey = gcd2(hey, it.second);
//return hey;
pnode l = NULL, mid = NULL, r = NULL;
split(root, l, r, mp(b, inf));
split(l, l, mid, mp(a-1, inf));
ll ans = 0;
if (mid != NULL)
ans = mid->res;
join(l, l, mid);
join(root, l, r);
return ans;
}
/*void print(pnode t){
if (t == NULL)
return;
print(t->lef);
printf(" (%d, %lld)", t->pos, t->val);
print(t->rig);
}
void print(){
/// this one
//printf("treap now:");
//for (auto it: mym)
// printf(" (%d, %lld)", it.first, it.second);
//printf("\n");
//return;
printf("treap now:");
print(root);
printf("\n");
}*/
};
ll tot = 0;
struct seg_tree{
struct node{
treap tree;
node *lef, *rig;
node(node *l = NULL, node *r = NULL){
tree = treap();
lef = l;
rig = r;
}
};
typedef node *pnode;
pnode root, null;
int mx;
/// this one
//vector<treap> myv;
seg_tree(int m = 0){
null = new node();
null->lef = null->rig = null;
root = null;
mx = m;
//printf("seg_tree initialized, mx = %d\n", mx);
//printf("starting gcd = %lld\n", root->tree.ask(0, 100));
///this one
//myv.resize(m);
}
pnode update(pnode t, int l, int r, int i, int j, ll v){
if (t == null)
t = new node(null, null);
t->tree.add(mp(j, i), v);
if (l == r)
return t;
int mid = (l+r)/2;
if (i <= mid)
t->lef = update(t->lef, l, mid, i, j, v);
else
t->rig = update(t->rig, mid+1, r, i, j, v);
return t;
}
void add(int r, int c, ll v){
/// this one
//myv[r].add(c, v);
//return;
root = update(root, 0, mx-1, r, c, v);
int deb = 0;
//if (63 <= r && r <= 83 && 31 <= c && c <= 42)
// deb = 1;
if (deb)
printf("r = %d, c = %d, v = %lld\n", r, c, v);
if (deb)
tot = gcd2(tot, v);
if (deb)
printf("tot = %lld\n", tot);
if (deb)
printf("rows:63-64, colss:37, ans = %lld\n", query(root, 0, mx-1, 63, 64, 37, 37));
//if (deb)
// print(root, 0, mx-1);
//printf("seg_tree::making (%d, %d) = %lld\n", r, c, v);
//printf("now root: %lld\n", query(root, 0, mx-1, 0, mx-1, 0, 1000000));
}
ll query(pnode t, int l, int r, int i, int j, int a, int b){
int deb = 0;
if (63 == i && j == 83 && 31 == a && b == 42)
deb = 1;
//if (deb)
// printf("query: l = %d, r = %d\n", l, r);
if (r < i || j < l)
return 0;
if (i <= l && r <= j){
//if (deb)
// printf("l = %d, r = %d, res = %lld\n", l, r, t->tree.ask(a, b)), t->tree.print();
//printf("query, l = %d, r = %d, i = %d, j = %d\n", l, r, i, j);
//t->tree.print();
return t->tree.ask(a, b);
}
int mid = (l+r)/2;
return gcd2(query(t->lef, l, mid, i, j, a, b), query(t->rig, mid+1, r, i, j, a, b));
}
ll ask(int ar, int br, int ac, int bc){
/// this one
//ll hey = 0;
//for (int i = ar; i <= br; i++)
// hey = gcd2(hey, myv[i].ask(ac, bc));
//return hey;
//printf("seg_tree::asking for (%d, %d) and (%d, %d)\n", ar, br, ac, bc);
//printf("null is: %lld\n", null->tree.ask(0, 10000));
return query(root, 0, mx-1, ar, br, ac, bc);
}
/*void print(pnode t, int l, int r){
if (l == r){
printf("row%d: ", l);
t->tree.print();
return;
}
int mid = (l+r)/2;
print(t->lef, l, mid);
print(t->rig, mid+1, r);
}*/
};
seg_tree data;
void init(int R, int C) {
data = seg_tree(R);
/*treap test;
int q = 10;
printf("you are allowed to ask up to %d questions\n", q);
while (q--){
int tp;
scanf("%d", &tp);
// tp == 1 - add
// tp == 0 - ask
if (tp == 1){
int p;
ll v;
scanf("%d %lld", &p, &v);
test.add(p, v);
test.print();
}
else{
int l, r;
scanf("%d %d", &l, &r);
printf("res: %lld\n", test.ask(l, r));
}
}*/
}
void update(int P, int Q, long long K) {
data.add(P, Q, K);
}
long long calculate(int ar, int ac, int br, int bc) {
return data.ask(ar, br, ac, bc);
}
