#include "game.h"
#include <iostream>
#include <algorithm>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
ll gcd(ll x, ll y) {
if(x < y)
swap(x, y);
while(y){
x %= y;
swap(x, y);
}
return x;
}
int n, m, dl, dr;
struct node{
node* p[2] = {nullptr, nullptr};
node* p1[2] = {nullptr, nullptr};
ll val = 0;
node* getp(int v){
if(!p[v])
p[v] = new node;
return p[v];
}
node* getp1(int v){
if(!p1[v])
p1[v] = new node;
return p1[v];
}
void merge(int tl, int tr, node* L, node* R, int pos){
if(!L && !R)
return;
if(tl == tr){
val = 0;
if(L)
val = gcd(L->val, val);
if(R)
val = gcd(R->val, val);
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm){
if(L)
L = L->p1[0];
if(R)
R = R->p1[0];
getp1(0)->merge(tl, tm, L, R, pos);
}
else{
if(L)
L = L->p1[1];
if(R)
R = R->p1[1];
getp1(1)->merge(tm + 1, tr, L, R, pos);
}
val = 0;
if(p1[0])
val = gcd(p1[0]->val, val);
if(p1[1])
val = gcd(p1[1]->val, val);
//cerr << tl << " " << tr << " " << val << " " << this << "s\n";
}
void upd1(int tl, int tr, int pos, ll _val){
if(tl == tr)
return void(val = _val);
int tm = (tl + tr) / 2;
//cerr << tl << " s " << tr << "\n";
if(pos <= tm)
getp1(0)->upd1(tl, tm, pos, _val);
else
getp1(1)->upd1(tm + 1, tr, pos, _val);
val = 0;
if(p1[0])
val = gcd(p1[0]->val, val);
if(p1[1])
val = gcd(p1[1]->val, val);
}
ll get1(int tl, int tr, int l, int r){
if(tl > r || l > tr)
return 0;
if(tl >= l && tr <= r)
return val;
int tm = (tl + tr) / 2;
ll left = (p1[0] ? p1[0]->get1(tl, tm, l, r): 0);
ll right = (p1[1] ? p1[1]->get1(tm + 1, tr, l, r): 0);
return gcd(left, right);
}
void upd(int tl, int tr, int pos, ll _val){
//cerr << tl << " " << tr << " b " << this << "\n";
if(tl == tr){
return void(upd1(1, m, dl, _val));
}
int tm = (tl + tr) / 2;
if(pos <= tm)
getp(0)->upd(tl, tm, pos, _val);
else
getp(1)->upd(tm + 1, tr, pos, _val);
merge(1, m, p[0], p[1], dl);
}
ll get(int tl, int tr, int l, int r){
if(tl > r || l > tr)
return 0;
if(tl >= l && tr <= r)
return get1(1, m, dl, dr);
int tm = (tl + tr) / 2;
ll left = (p[0] ? p[0]->get(tl, tm, l, r): 0);
ll right = (p[1] ? p[1]->get(tm + 1, tr, l, r): 0);
//cerr << tl << " " << tr << " " << left << " z " << right << "\n";
return gcd(left, right);
}
}root;
void init(int R, int C) {
n = R, m = C;
}
void update(int P, int Q, ll K) {
// cerr << "was1\n";
dl = Q + 1;
//cerr << P + 1 << " " << Q + 1 << "\n";
root.upd(1, n, P + 1, K);
// cerr << "was\n";
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
//cerr << "were\n";
dl = Q + 1, dr = V + 1;
//cerr << P + 1 << " " << U + 1 << " " << dl << " " << dr << "\n";
ll tmp = root.get(1, n, P + 1, U + 1);
// cerr << tmp << "\n";
return tmp;
}
