#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
long long gcd2(long long X, long long Y)
{
long long tmp;
while (X != Y && Y != 0)
{
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct tree
{
tree *l = NULL, *r = NULL;
int lv, rv;
int res = 0;
tree(int lv, int rv) : lv(lv), rv(rv) {}
void enlarge()
{
int m = (lv + rv) >> 1;
if (l == NULL)
l = new tree(lv, m);
if (r == NULL)
r = new tree(m, rv);
}
int get(int L, int R)
{
enlarge();
if (L <= lv and rv <= R)
{
return res;
}
if (rv <= L or R <= lv)
return 0;
assert(rv - lv > 0);
return gcd2(l->get(L, R), r->get(L, R));
}
void set(int pos, int val)
{
enlarge();
res = gcd2(res, val);
if (rv - lv == 1)
return;
assert(rv - lv > 0);
int m = (lv + rv) >> 1;
if (pos < m)
l->set(pos, val);
else
r->set(pos, val);
}
};
struct TREE
{
TREE *l = NULL, *r = NULL;
int lv, rv, maxY;
tree *res;
TREE(int lv, int rv, int maxY) : lv(lv), rv(rv), maxY(maxY) { res = new tree(0, maxY); }
void enlarge()
{
int m = (lv + rv) >> 1;
if (l == NULL)
l = new TREE(lv, m, maxY);
if (r == NULL)
r = new TREE(m, rv, maxY);
}
int get(int L, int R, int lx, int ly)
{
enlarge();
if (L <= lv and rv <= R)
{
return res->get(lx, ly);
}
if (rv <= L or R <= lv)
return 0;
return gcd2(l->get(L, R, lx, ly), r->get(L, R, lx, ly));
}
void set(int x, int y, int val)
{
enlarge();
res->set(y, val);
if (rv - lv == 1)
return;
int m = (lv + rv) >> 1;
if (x < m)
l->set(x, y, val);
else
r->set(x, y, val);
}
};
TREE help(0, 1e9 + 10, 1e9 + 10);
vector<vector<int>> els;
void init(int R, int C)
{
els.resize(R, vector<int>(C));
/* ... */
}
void update(int P, int Q, long long K)
{
/* ... */
els[P][Q] = K;
}
long long calculate(int P, int Q, int U, int V)
{
/* ... */
int L = min(P, U);
int R = max(P, U) + 1;
int l = min(Q, V);
int r = max(Q, V) + 1;
int res = 0;
for (int x = L; x < R; ++x)
for (int y = l; y < r; ++y)
res = gcd2(res, els[x][y]);
return res;
}
// /////////////////////
// #include <stdio.h>
// #include <stdlib.h>
// #include <assert.h>
// #include <vector>
// #include "game.h"
// #define MAX_SIZE 1000000000
// #define MAX_N 272000
// int main()
// {
// int R, C, N;
// int P, Q, U, V;
// long long K;
// int i, type;
// assert(scanf("%d", &R) == 1);
// assert(scanf("%d", &C) == 1);
// assert(scanf("%d", &N) == 1);
// init(R, C);
// std::vector<long long> answers;
// for (i = 0; i < N; i++)
// {
// assert(scanf("%d", &type) == 1);
// if (type == 1)
// {
// assert(scanf("%d%d%lld", &P, &Q, &K) == 3);
// update(P, Q, K);
// }
// else if (type == 2)
// {
// assert(scanf("%d%d%d%d", &P, &Q, &U, &V) == 4);
// answers.push_back(calculate(P, Q, U, V));
// }
// }
// for (auto answer : answers)
// {
// printf("%lld\n", answer);
// }
// return 0;
// }
