#include "game.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
#include <chrono>
#include<random>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
const int mxn=3e5,inf=1e18;
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;
}
mt19937_64 rng(5);
struct node{
node *l,*r;
int col,row,val,G,p;
node(int x,int y,int z):l(0),r(0),p(rng()),row(x),col(y),val(z),G(z){};
};
struct treap{
node *root=0;
int get(node *&a){
if(a==NULL)return 0;
return a->G;
}
void pull(node *&x){
if(x==NULL)return;
x->G=gcd(x->val,gcd(get(x->l),get(x->r)));
}
void split(node *&L,node *&R,node *cur,int row,int col){
if(cur==NULL)return void(L=R=NULL);
if(cur->col<=col&&cur->row<=row){
split(cur->r,R,cur->r,row,col);
L=cur;
}
else{
split(L,cur->l,cur->l,row,col);
R=cur;
}
pull(L);
pull(R);
}
void merge(node *a,node *b,node *&cur){
if(a==NULL)return void(cur=b);
if(b==NULL)return void(cur=a);
if(a->p<=b->p)merge(a->r,b,a->r),cur=a;
else merge(a,b->l,b->l),cur=b;
pull(cur);
}
bool change(node *&cur,int x,int y,int z){
if(cur==NULL)return 0;
if(cur->r!=NULL){
if(change(cur->r,x,y,z)){
pull(cur);
return 1;
}
return 0;
}
else if(cur->row==x&&cur->col==y){
cur->val=cur->G=z;
pull(cur);
return 1;
}
pull(cur);
return 0;
}
};
treap row[mxn+10];
void init(int32_t R, int32_t C){
return;
}
void print(node *&x){
if(x==NULL)return;
cout<<x->val<<" "<<x->G<<"P\n";
}
void update(int32_t P, int32_t Q, long long K){
node *x=new node(P,Q,K);
if(row[P].root==NULL)row[P].root=x;
else{
node *R=NULL;
row[P].split(row[P].root,R,row[P].root,P,Q);
if(row[P].change(row[P].root,P,Q,K))return void(row[P].merge(row[P].root,R,row[P].root));
row[P].merge(row[P].root,x,row[P].root);
row[P].merge(row[P].root,R,row[P].root);
}
}
//col U->V
int get(int x,int U,int V){
node *L=NULL,*R=NULL;
if(row[x].root==NULL)return 0;
row[x].split(L,row[x].root,row[x].root,inf,U-1);
row[x].split(row[x].root,R,row[x].root,inf,V);
int ans=(row[x].root==NULL)?0:row[x].root->G;
row[x].merge(L,row[x].root,row[x].root);
row[x].merge(row[x].root,R,row[x].root);
return ans;
}
long long calculate(int32_t P, int32_t Q, int32_t U, int32_t V){
int ans=0;
for(int i=P;i<=U;i++)ans=gcd(ans,get(i,Q,V));
return ans;
}
