#include <bits/stdc++.h>
#include "game.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define oorta ((bbas+sson)/2)
#define mod 1000000007
#define MAXN 20000005
using namespace std;
// #define fail(s, x...) do { \
// fprintf(stderr, s "\n", ## x); \
// exit(1); \
// } while(0)
typedef long long ll;
int n, m, son1, son2, sol[MAXN], sag[MAXN], seg[MAXN], sl[MAXN], sg[MAXN], bas[MAXN], son[MAXN];
ll val[MAXN];
ll gcd2(ll X, ll Y) {
if(X == 0 || Y == 0) {
return X + Y;
}
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int ver(int k){
if(!k)return 0;
if(!seg[k]){
son2++;
bas[son2] = 1;
son[son2] = m;
return seg[k] = son2;
}
else
return seg[k];
}
int yeniver(int bs, int sn){
++son2;
bas[son2]=bs;
son[son2]=sn;
return son2;
}
int slver(int k){
return (!sl[k])?sl[k] = ++son2:sl[k];
}
int sgver(int k){
return (!sg[k])?sg[k] = ++son2:sg[k];
}
int solver(int k){
return (!sol[k])?sol[k] = ++son1:sol[k];
}
int sagver(int k){
return (!sag[k])?sag[k] = ++son1:sag[k];
}
ll qu2(int k, int x, int y){
if(!k or bas[k] > y or son[k] < x)
return 0;
if(bas[k] >= x and son[k] <= y)
return val[k];
return gcd2(qu2(sl[k], x, y), qu2(sg[k], x, y));
}
ll qu1(int k, int bas, int son, int x, int y, int xx, int yy){
if(!k or bas > y or son < x)
return 0;
if(bas >= x and son <= y)
return qu2(seg[k], xx, yy);
return gcd2(qu1(sol[k], bas, orta, x, y, xx, yy), qu1(sag[k], orta + 1, son, x, y, xx, yy));
}
void up2(int k, int x, ll z){
if(bas[k] == son[k]){
val[k] = z;
return;
}
int git = (x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k];
if(!git){
int of = ((x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k]) = yeniver(x, x);
val[of] = z;
}
else if(bas[git] <= x and son[git] >= x)
up2(git, x, z);
else{
int bbas = bas[k], sson = son[k];
do{
if(x <= oorta)
sson = oorta;
else
bbas = oorta + 1;
}while((x <= oorta) == (bas[git] <= oorta) );
int of = ((x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k]) = yeniver(bbas, sson);
(bas[git] <= oorta ? sl[of] : sg[of]) = git;
up2(of, x, z);
}
val[k] = gcd2(val[sl[k]], val[sg[k]]);
}
void up1(int k, int bas, int son, int x, int y, ll z){
if(bas == son){
up2(ver(k), y, z);
return;
}
if(x <= orta)
up1(solver(k), bas, orta, x, y, z);
else
up1(sagver(k), orta + 1, son, x, y, z);
z = gcd2(qu2(seg[sol[k]], y, y), qu2(seg[sag[k]], y, y));
up2(ver(k), y, z);
}
void init(int R, int C) {
n = R;m = C;
son1++;
}
void update(int p, int q, ll k) {
up1(1, 1, n, p + 1, q + 1, k);
}
ll calculate(int p, int q, int u, int v) {
return qu1(1, 1, n, p+1, u+1, q+1, v+1);
}
// int main() {
// int R, C, N;
// int P, Q, U, V;
// long long K;
// int i, type;
// int res;
// FILE *f = fopen("in.txt", "r");
// if (!f)
// fail("Failed to open input file.");
// res = fscanf(f, "%d", &R);
// res = fscanf(f, "%d", &C);
// res = fscanf(f, "%d", &N);
// init(R, C);
// for (i = 0; i < N; i++) {
// res = fscanf(f, "%d", &type);
// if (type == 1) {
// res = fscanf(f, "%d%d%lld", &P, &Q, &K);
// update(P, Q, K);
// } else if (type == 2) {
// res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
// printf("%lld\n", calculate(P, Q, U, V));
// } else
// fail("Invalid action type in input file.");
// }
// fclose(f);
// return 0;
// }
