#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
typedef long long ll;
//#define ll long long
int rmax, cmax;
inline ll gcd(ll a, ll b) {
if(b>a) return gcd(b, a);
if(b==0) return a;
if(a%2==0 && b%2==0) return 2*gcd(a/2, b/2);
if(a%2==0 && b%2==1) return gcd(a/2, b);
if(a%2==1 && b%2==0) return gcd(a, b/2);
return gcd((a-b)/2, b);
}
ll DIGIT_BITS=30;
ll BASE = 1 << DIGIT_BITS;
ll nbits(ll n) {
return floor(log2(n))+1;
}
inline ll lehmer_gcd(ll a, ll b) {
if(a==b) return a;
if(a==0) return b;
if(b==0) return a;
if(a<b) return gcd(b, a);
while(b >= BASE) {
ll push = nbits(a) - DIGIT_BITS;
ll x = a >> push;
ll y = b >> push;
ll A=1, B=0, C=0, D=1;
while(1) {
if(y+C==0 || y+D==0) break;
ll q = (x+A) / (y+C);
if(q!=(x+B)/(y+D)) break;
ll tempA=A, tempB=B, tempx=x;
A=C; B=D; x=y;
C=tempA-q*C; D=tempB-q*D; y=tempx-q*y;
}
if(B) {
ll tempa = a;
a = A*a + B*b;
b = C*tempa + D*b;
}
else {
ll tempa = a;
a = b;
b = tempa % b;
}
}
return gcd(a, b);
}
typedef struct InnerTree {
int l;
int r;
ll Data;
struct InnerTree* Left;
struct InnerTree* Right;
InnerTree(int inl, int inr): l(inl), r(inr) {Data=0; Left=Right=NULL;}
}InnerTree;
typedef struct OuterTree {
int l;
int r;
InnerTree* Data;
struct OuterTree* Left;
struct OuterTree* Right;
OuterTree(int inl, int inr) : l(inl), r(inr) {Data=NULL; Left=Right=NULL;}
}OuterTree;
ll queryIN(InnerTree* TN, int l, int r) {
if(TN==NULL) return 0;
if(r < TN->l || TN->r < l) return 0;
if(l <= TN->l && TN->r <= r) return TN->Data;
return gcd(queryIN(TN->Left, l, r), queryIN(TN->Right, l, r));
}
ll queryOUT(OuterTree *TN, int cl, int cr, int rl, int rr) {
if(TN==NULL) return 0;
if(cr < TN->l || TN->r < cl) return 0;
if(cl <= TN->l && TN->r <= cr) return queryIN(TN->Data, rl, rr);
return gcd(queryOUT(TN->Left, cl, cr, rl, rr), queryOUT(TN->Right, cl, cr, rl, rr));
}
ll updateIN(InnerTree* TN, int r, ll k) {
if(TN->l == TN->r) {
if(TN->Data == k) return -2;
TN->Data = k;
return k;
}
ll other;
if(r <= (TN->l + TN->r)/2) {
if(TN->Left == NULL) {
TN->Left = new InnerTree(TN->l, (TN->l + TN->r)/2);
}
other = updateIN(TN->Left, r, k);
if(other < 0) return other;
other = gcd((TN->Right == NULL ? 0 : TN->Right->Data), other);
}
else {
if(TN->Right == NULL) {
TN->Right = new InnerTree((TN->l + TN->r)/2 + 1, TN->r);
}
other = updateIN(TN->Right, r, k);
if(other < 0) return other;
other = gcd((TN->Left == NULL ? 0 : TN->Left->Data), other);
}
if(other == TN->Data) return -1;
TN->Data=other;
return other;
}
ll updateOUT(OuterTree* TN, int r, int c, ll k) {
if(TN->Data == NULL) {
TN->Data = new InnerTree(0, rmax);
}
if(TN->l == TN->r) {
if(updateIN(TN->Data, r, k) == -2) return -1;
return k;
}
ll rightk;
if(c <= (TN->l + TN->r)/2) {
if(TN->Left == NULL) {
TN->Left = new OuterTree(TN->l, (TN->l + TN->r)/2);
}
rightk = updateOUT(TN->Left, r, c, k);
if(rightk < 0) return rightk;
rightk = gcd(rightk, queryOUT(TN->Right, (TN->l + TN->r)/2+1, TN->r, r, r));
}
else {
if(TN->Right == NULL) {
TN->Right = new OuterTree((TN->l + TN->r)/2+1, TN->r);
}
rightk = updateOUT(TN->Right, r, c, k);
if(rightk < 0 ) return rightk;
rightk = gcd(rightk, queryOUT(TN->Left, TN->l, (TN->l + TN->r)/2, r, r));
}
updateIN(TN->Data, r, rightk);
return rightk;
}
int main() {
//ifstream cin;
//cin.open("input.txt");
int r, c, n, command;
int cl, cr, rl, rr;
ll k;
int i, j;
cin >> r >> c >> n;
OuterTree * OutTree = new OuterTree(0, c-1);
rmax = r-1;
cmax = c-1;
for(i=0; i<n; i++) {
cin >> command;
if(command==1) {
cin >> rl >> cl;
cin >> k;
updateOUT(OutTree, rl, cl, k);
}
else {
cin >> rl >> cl >> rr >> cr;
cout << queryOUT(OutTree, cl, cr, rl, rr) << endl;
}
}
//cin.close();
return 0;
}
글쓰기