#include "game.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
#define lol long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scanl(a) scanf("%lld",&a);
#define scanll(a,b) scanf("%lld %lld",&a, &b);
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define eps 1e-12
vector <vector <lol> > der;
int n,m;
void init(int R, int C) {
n = R-1;
m = C-1;
R+=R;
C+=C;
if(min(R,C) <= 100)der.assign(R+R-1, vector <lol> (C+C-1));
else der.assign(min(5000,R+R-1), vector <lol> (min(5000,C+C-1)));
}
void update_y(int vx,int lx,int rx,int vy,int ly,int ry,int x,int y,lol k){
if (ly == ry){
if (lx == rx){
der[vx][vy] = k;
}
else
der[vx][vy] = __gcd(der[vx<<1][vy],der[(vx<<1)+1][vy]);
}
else {
int m = ly+ry>>1;
if (m < y)
update_y(vx,lx,rx,(vy<<1)+1,m+1,ry,x,y,k);
else
update_y(vx,lx,rx,vy<<1,ly,m,x,y,k);
der[vx][vy] = __gcd(der[vx][vy<<1],der[vx][(vy<<1)+1]);
}
}
void update_x(int vx,int lx,int rx,int x,int y,lol k){
if (lx != rx){
int m = lx+rx>>1;
if (x > m){
update_x((vx<<1)+1,m+1,rx,x,y,k);
}
else {
update_x((vx<<1),lx,m,x,y,k);
}
}
update_y(vx,lx,rx,1,0,m,x,y,k);
}
lol gcd_y(int vx,int lx,int rx,int vy,int ly,int ry,int x1,int y1,int x2,int y2){
if (y1 > ry || y2 < ly)ret 0;
if (y1 <= ly && ry <= y2)ret der[vx][vy];
int m = ly+ry>>1;
ret __gcd(gcd_y(vx,lx,rx,vy<<1,ly,m,x1,y1,x2,y2),gcd_y(vx,lx,rx,(vy<<1)+1,m+1,ry,x1,y1,x2,y2));
}
lol gcd_x(int vx,int lx,int rx,int x1,int y1,int x2,int y2){
if (x1 > rx || x2 < lx)ret 0;
if (x1 <= lx && rx <= x2){
ret gcd_y(vx,lx,rx,1,0,m,x1,y1,x2,y2);
}
else {
int m = lx+rx>>1;
ret __gcd(gcd_x(vx<<1,lx,m,x1,y1,x2,y2),gcd_x((vx<<1)+1,m+1,rx,x1,y1,x2,y2));
}
}
void update(int P, int Q, lol K) {
update_x(1,0,n,P,Q,K);
}
lol calculate(int P, int Q, int U, int V) {
ret gcd_x(1,0,n,P,Q,U,V);
}
