#include "game.h"
#include <iostream>
#include <vector>
#include <numeric>
#define ll long long
using namespace std;
ll A[22000], sz;
ll gcd(ll a, ll b) {
if (!b) return a;
else if (!a) return b;
else return gcd(b%a, a);
}
struct SegTree{
struct Node{
ll val;
int chl;
int chr;
};
int cnt = 0;
Node st[20000000];
void get(int &id) {
if (id != -1) return;
st[cnt] = {0, -1, -1};
id = cnt++;
}
void updateC(int &id, int idl, int idr, int l, int r, int y, ll w) {
get(id);
if (l == r) {
if (idl == -1 && idr == -1) st[id].val = w;
else st[id].val = gcd((idl != -1 ? st[idl].val : 0), (idr != -1 ? st[idr].val : 0));
return;
}
int mid = (l+r)/2;
if (st[id].chr == -1e9) {
int ty = st[id].chl;
ll tw = st[id].val;
st[id] = {0, -1, -1};
if (ty <= mid) {
int tmp = st[id].chl, tmpchl = (idl != -1 ? st[idl].chl : -1), tmpchr = (idr != -1 ? st[idr].chl : -1);
if (idl != -1 && st[idl].chr == -1e9) {
if (st[idl].chl <= mid) tmpchl = idl;
else tmpchl = -1;
}
if (idr != -1 && st[idr].chr == -1e9) {
if (st[idr].chl <= mid) tmpchr = idr;
else tmpchr = -1;
}
updateC(tmp, tmpchl, tmpchr, l, mid, ty, tw);
st[id].chl = tmp;
}
else {
int tmp = st[id].chr, tmpchl = (idl != -1 ? st[idl].chr : -1), tmpchr = (idr != -1 ? st[idr].chr : -1);
if (idl != -1 && st[idl].chr == -1e9) {
if (st[idl].chl > mid) tmpchl = idl;
else tmpchl = -1;
}
if (idr != -1 && st[idr].chr == -1e9) {
if (st[idr].chl > mid) tmpchr = idr;
else tmpchr = -1;
}
updateC(tmp, tmpchl, tmpchr, mid+1, r, ty, tw);
st[id].chr = tmp;
}
}
else if (id + 1 == cnt) {
st[id].val = w;
st[id].chl = y;
st[id].chr = -1e9;
return;
}
if (y <= mid) {
int tmp = st[id].chl, tmpchl = (idl != -1 ? st[idl].chl : -1), tmpchr = (idr != -1 ? st[idr].chl : -1);
if (idl != -1 && st[idl].chr == -1e9) {
if (st[idl].chl <= mid) tmpchl = idl;
else tmpchl = -1;
}
if (idr != -1 && st[idr].chr == -1e9) {
if (st[idr].chl <= mid) tmpchr = idr;
else tmpchr = -1;
}
updateC(tmp, tmpchl, tmpchr, l, mid, y, w);
st[id].chl = tmp;
}
else {
int tmp = st[id].chr, tmpchl = (idl != -1 ? st[idl].chr : -1), tmpchr = (idr != -1 ? st[idr].chr : -1);
if (idl != -1 && st[idl].chr == -1e9) {
if (st[idl].chl > mid) tmpchl = idl;
else tmpchl = -1;
}
if (idr != -1 && st[idr].chr == -1e9) {
if (st[idr].chl > mid) tmpchr = idr;
else tmpchr = -1;
}
updateC(tmp, tmpchl, tmpchr, mid+1, r, y, w);
st[id].chr = tmp;
}
//cout << id << " " << st[id].chl << " " << st[id].chr << endl;
st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
}
void updateR(int &id, int l, int r, int x, int y, ll w) {
get(id);
if (id+1 == cnt) {
int tmp = -1;
get(tmp);
}
int tmp = id+1;
if (l == r) {
updateC(tmp, -1, -1, 0, (int)1e9-1, y, w);
st[id].val = st[id+1].val;
return;
}
int mid = (l+r)/2;
if (x <= mid) {
int tmp = st[id].chl;
updateR(tmp, l, mid, x, y, w);
st[id].chl = tmp;
}
else {
int tmp = st[id].chr;
updateR(tmp, mid+1, r, x, y, w);
st[id].chr = tmp;
}
updateC(tmp, (st[id].chl != -1 ? st[id].chl+1 : -1), (st[id].chr != -1 ? st[id].chr+1 : -1), 0, (ll)1e9-1, y, w);
st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
}
ll queryC(int id, int l, int r, int ql, int qr) {
if (id == -1 || qr < l || r < ql) return 0;
else if (ql <= l && r <= qr) {
return st[id].val;
}
if (st[id].chr == -1e9) {
if (ql <= st[id].chl && st[id].chl <= qr) return st[id].val;
else return 0;
}
int mid = (l+r)/2;
return gcd(queryC(st[id].chl, l, mid, ql, qr), queryC(st[id].chr, mid+1, r, ql, qr));
}
ll queryR(int id, int l, int r, int ql, int qr, int qx, int qy) {
if (id == -1 || qr < l || r < ql) return 0;
else if (ql <= l && r <= qr) return queryC(id+1, 0, (int)1e9-1, qx, qy);
int mid = (l+r)/2;
return gcd(queryR(st[id].chl, l, mid, ql, qr, qx, qy), queryR(st[id].chr, mid+1, r, ql, qr, qx, qy));
}
}ST;
void init(int R, int C) {
int rt = -1;
ST.get(rt);
}
void update(int P, int Q, long long K) {
int rt = 0;
ST.updateR(rt, 0, (int)1e9-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
int rt = 0;
return ST.queryR(rt, 0, (int)1e9-1, P, U, Q, V);
}
