#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
ll gcd(ll X, ll Y)
{
if(X > Y) swap(X,Y);
while(X > 0)
{
Y = Y % X;
swap(X,Y);
}
return Y;
}
struct node
{
int l = 0;
int r = (1 << 30)-1;
ll g = 0;
node* left;
node* right;
node()
{
left = NULL;
right = NULL;
}
ll get_gcd(int l2, int r2)
{
if(l >= l2 && r <= r2) return g;
if(r < l2 || l > r2) return 0;
return gcd((left != NULL ? left -> get_gcd(l2,r2): 0), (right != NULL ? right -> get_gcd(l2,r2) : 0));
}
void change_val(int p, ll x)
{
if(l == r)
{
g = x;
return;
}
if(p <= (l+r)/2)
{
if(left == NULL)
{
left = new node;
left -> l = p;
left -> r = p;
left -> g = x;
g = gcd(g,x);
}
else
{
if(left -> l <= p && left -> r >= p)
{
left -> change_val(p,x);
g = gcd(left -> g, (right != NULL ? right -> g : 0));
return;
}
int cur_l = l;
int cur_r = r;
while(true)
{
if((cur_l+cur_r)/2 >= p && (cur_l+cur_r)/2 >= left -> l)
{
cur_r = (cur_l+cur_r)/2;
}
else if((cur_l+cur_r)/2+1 <= p && (cur_l+cur_r)/2+1 <= left -> l)
{
cur_l = (cur_l+cur_r)/2+1;
}
else
{
node* left2 = new node;
left2 -> l = cur_l;
left2 -> r = cur_r;
node* total_new = new node;
total_new -> l = p;
total_new -> r = p;
total_new -> g = x;
if((cur_l+cur_r/2) >= p)
{
left2 -> right = left;
left2 -> left = total_new;
}
else
{
left2 -> left = left;
left2 -> right = total_new;
}
left2 -> g = gcd(left -> g, total_new -> g);
left = left2;
g = gcd(left -> g, (right != NULL ? right -> g : 0));
return;
}
}
}
}
else
{
if(right == NULL)
{
right = new node;
right -> l = p;
right -> r = p;
right -> g = x;
g = gcd(g,x);
}
else
{
if(right -> l <= p && right -> r >= p)
{
right -> change_val(p,x);
g = gcd(right -> g, (left != NULL ? left -> g : 0));
return;
}
int cur_l = l;
int cur_r = r;
while(true)
{
if((cur_l+cur_r)/2 >= p && (cur_l+cur_r)/2 >= right -> l)
{
cur_r = (cur_l+cur_r)/2;
}
else if((cur_l+cur_r)/2+1 <= p && (cur_l+cur_r)/2+1 <= right -> l)
{
cur_l = (cur_l+cur_r)/2+1;
}
else
{
node* right2 = new node;
right -> l = cur_l;
right -> r = cur_r;
node* total_new = new node;
total_new -> l = p;
total_new -> r = p;
total_new -> g = x;
if((cur_l+cur_r/2) >= p)
{
right2 -> right = right;
right2 -> left = total_new;
}
else
{
right2 -> left = right;
right2 -> right = total_new;
}
right2 -> g = gcd(right -> g, total_new -> g);
right = right2;
g = gcd(right -> g, (left != NULL ? left -> g : 0));
return;
}
}
}
}
}
};
struct node2
{
int l = 0;
int r = (1 << 30)-1;
node2* left;
node2* right;
node* tr;
node2()
{
left = NULL;
right = NULL;
tr = new node;
}
void upd(int p1, int p2, ll x)
{
tr -> change_val(p2,x);
if(l == r) return;
if(p1 <= (l+r)/2)
{
if(left == NULL)
{
left = new node2;
left -> l = l;
left -> r = (l+r)/2;
}
left -> upd(p1,p2,x);
}
else
{
if(right == NULL)
{
right = new node2;
right -> l = (l+r)/2+1;
right -> r = r;
}
right -> upd(p1,p2,x);
}
}
ll get_gcd(int l1, int r1, int l2, int r2)
{
if(l >= l1 && r <= r1) return tr -> get_gcd(l2,r2);
if(r < l1 || l > r1) return 0;
return gcd((left != NULL ? left -> get_gcd(l1,r1,l2,r2) : 0),(right != NULL ? right -> get_gcd(l1,r1,l2,r2) : 0));
}
};
node2 root;
void init(int R, int C)
{
}
void update(int P, int Q, ll K)
{
root.upd(P,Q,K);
}
ll calculate(int P, int Q, int U, int V)
{
return root.get_gcd(P,U,Q,V);
}
