#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <utility>
#include "game.h"
typedef long long ll;
const int N = 300010;
using namespace std;
typedef pair<int, int> ii;
//from errorgorn
ll rd()
{
ll k = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
k = (k << 1) + (k << 3) + (c ^ 48);
c = getchar();
}
return f > 0 ? k : -k;
}
void wr(ll x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar(x % 10 + '0');
}
inline long long func(long long X, long long Y)
{
long long tmp;
while (X != Y && Y != 0)
{
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
//return X + Y;
}
/*
int __builtin_clz(int x) {
if (!x)return 32;
int ret = 0;
//if (!(x & 0xFFFFFFFF00000000ll)) ret += 32, x <<= 32;
if (!(x & 0xFFFF0000)) ret += 16, x <<= 16;
if (!(x & 0xFF000000)) ret += 8, x <<= 8;
if (!(x & 0xF0000000)) ret += 4, x <<= 4;
if (!(x & 0xC0000000)) ret += 2, x <<= 2;
if (!(x & 0x80000000)) ret += 1, x <<= 1;
return ret;
}
*/
ii lca(int l, int r, int pos)
{ // find lca of 2 nodes
if (pos < l)
{
int p = 32 - __builtin_clz(pos ^ l);
int lp = (pos >> p) << p;
return ii(lp, lp + (1 << p) - 1);
}
if (r < pos)
{
int p = 32 - __builtin_clz(r ^ pos);
int lp = (l >> p) << p;
return ii(lp, lp + (1 << p) - 1);
}
return ii(pos, 0);
}
struct node
{
int s, e, m;
long long val = 0;
node *l = nullptr, *r = nullptr;
node(int _s, int _e)
{
s = _s, e = _e, m = (s + e) >> 1;
}
bool inside(int i)
{
return s <= i && i <= e;
}
void update(int i, long long j)
{
if (s == e)
val = j;
else
{
if (i <= m)
{
if (l == nullptr)
l = new node(i, i);
else if (!l->inside(i))
{
node *temp = l;
ii child = lca(l->s, l->e, i);
l = new node(child.first, child.second);
if (temp->e <= l->m)
l->l = temp;
else
l->r = temp;
}
l->update(i, j);
}
else
{
if (r == nullptr)
r = new node(i, i);
else if (!r->inside(i))
{
node *temp = r;
ii child = lca(r->s, r->e, i);
r = new node(child.first, child.second);
if (temp->e <= r->m)
r->l = temp;
else
r->r = temp;
}
r->update(i, j);
}
val = func((l == nullptr) ? 0 : l->val, (r == nullptr) ? 0 : r->val);
}
}
long long query(int i, int j)
{
if (i <= s && e <= j)
return val;
else if (j <= m)
return (l == nullptr) ? 0 : l->query(i, j);
else if (m < i)
return (r == nullptr) ? 0 : r->query(i, j);
else
return func((l == nullptr) ? 0 : l->query(i, m), (r == nullptr) ? 0 : r->query(m + 1, j));
}
node *clone()
{
node *res = new node(s, e);
res->val = val;
res->l = (l == nullptr) ? nullptr : l->clone();
res->r = (r == nullptr) ? nullptr : r->clone();
return res;
}
};
struct node2d
{
int s, e, m;
node *val = new node(0, (1 << 30) - 1);
node2d *l = nullptr, *r = nullptr;
node2d(int _s, int _e)
{
s = _s, e = _e, m = s + e >> 1;
}
bool inside(int i)
{
return s <= i && i <= e;
}
void update(int i, int j, long long k)
{
if (s == e)
val->update(j, k);
else
{
if (i <= m)
{
if (l == nullptr)
l = new node2d(i, i);
else if (!l->inside(i))
{
node2d *temp = l;
ii child = lca(l->s, l->e, i);
l = new node2d(child.first, child.second);
if (temp->e <= l->m)
l->l = temp;
else
l->r = temp;
l->val = temp->val->clone();
}
l->update(i, j, k);
}
else
{
if (r == nullptr)
r = new node2d(i, i);
else if (!r->inside(i))
{
node2d *temp = r;
ii child = lca(r->s, r->e, i);
r = new node2d(child.first, child.second);
if (temp->e <= r->m)
r->l = temp;
else
r->r = temp;
r->val = temp->val->clone();
}
r->update(i, j, k);
}
val->update(j, func((l == nullptr) ? 0 : l->val->query(j, j), (r == nullptr) ? 0 : r->val->query(j, j)));
}
}
long long query(int i, int j, int i2, int j2)
{
if (i <= s && e <= j)
return val->query(i2, j2);
else if (j <= m)
return (l == nullptr) ? 0 : l->query(i, j, i2, j2);
else if (m < i)
return (r == nullptr) ? 0 : r->query(i, j, i2, j2);
else
return func((l == nullptr) ? 0 : l->query(i, m, i2, j2), (r == nullptr) ? 0 : r->query(m + 1, j, i2, j2));
}
} *root = new node2d(0, (1 << 30) - 1);
void init(int R, int C)
{
}
void update(int P, int Q, long long K)
{
root->update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
return root->query(P, U, Q, V);
}
void test_interaction()
{
int n = rd(), m = rd();
init(n, m);
int q = rd();
while(q--)
{
int op = rd();
//op 1 : update single point
if (op == 1)
{
int x = rd(), y = rd(); ll w = rd();
update(x, y, w);
}
//op 2 : 2D gcd query
else
{
int xl = rd(), yl = rd(), xr = rd(), yr = rd();
wr(calculate(xl, yl, xr, yr)), putchar('\n');
}
}
}
