#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
struct node {
int l=-1,r=-1;
ll s=0;
};
struct node2d {
int root=-1,l=-1,r=-1;
};
int nxt=1, nxt2d=1;
const int sz=1<<30;
const int tsz=1e7;
vector<node> t(tsz);
node2d st[(int)30e4];
ll query(int v, int l, int r, int lx, int rx) {
if (v==-1) return 0;
if (rx<=l || r<=lx) return 0;
if (lx<=l && r<=rx) return t[v].s;
int m=(l+r)>>1;
ll lq = query(t[v].l,l,m,lx,rx);
ll rq = query(t[v].r,m,r,lx,rx);
return __gcd(lq,rq);
}
ll query2d(int v, int l, int r, int lx, int rx, int ly, int ry) {
if (v==-1) return 0;
if (rx<=l || r<=lx) return 0;
if (lx<=l && r<=rx) {
return query(st[v].root,0,sz,ly,ry);
}
int m=(l+r)>>1;
ll lq = query2d(st[v].l,l,m,lx,rx,ly,ry);
ll rq = query2d(st[v].r,m,r,lx,rx,ly,ry);
return __gcd(lq,rq);
}
ll query2d(int a, int b, int l, int r) {
return query2d(0,0,sz,a,b,l,r);
}
#define set sett
void set(int v, int l, int r, int i, ll x) {
if (r-l==1) {
t[v].s=x;
return;
}
int m=(l+r)>>1;
if (i<m) {
if (t[v].l==-1) t[v].l=nxt++;
set(t[v].l,l,m,i,x);
} else {
if (t[v].r==-1) t[v].r=nxt++;
set(t[v].r,m,r,i,x);
}
t[v].s=__gcd( (t[v].l==-1)?0:t[t[v].l].s, (t[v].r==-1)?0:t[t[v].r].s );
}
void set2d(int v, int l, int r, int a, int b, ll x) {
if (st[v].root==-1) st[v].root=nxt++;
if (r-l==1) {
set(st[v].root,0,sz,b,x);
return;
}
int m=(l+r)>>1;
ll y;
if (a<m) {
if (st[v].l==-1) st[v].l=nxt2d++;
set2d(st[v].l,l,m,a,b,x);
x=query2d(st[v].l,l,m,l,m,b,b+1);
y=query2d(st[v].r,m,r,m,r,b,b+1);
} else {
if (st[v].r==-1) st[v].r=nxt2d++;
set2d(st[v].r,m,r,a,b,x);
x=query2d(st[v].l,l,m,l,m,b,b+1);
y=query2d(st[v].r,m,r,m,r,b,b+1);
}
set(st[v].root,0,sz,b,__gcd(x,y));
}
void set2d(int a, int b, ll x) {
set2d(0,0,sz,a,b,x);
}
void init(int n, int m) {
}
void update(int p, int q, ll k) {
set2d(p,q,k);
}
ll calculate(int p, int q, int u, int v) {
return query2d(p,u+1,q,v+1);
}
