#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long ;
const int N = 1e5+5 ;
ll Mat[15][N] ; // ,st[15][4*N];
unordered_map<int,unordered_map<int,ll>> st;
int ROW , COL ;
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;
}
int l(int u){return (u*2+1);}
int r(int u ){return (u*2+2);}
void Update(int Row , int Ind , int L , int R ,int node,ll val){
// cout << "Update " << L<<" " << R << "node " << node <<endl;
if( L > R )return ;
if( L == R ){
st[Row][node]=val;
return ;
}
int mid = (L+R)/2 ;
if( Ind <= mid )
Update(Row,Ind,L,mid,l(node),val);
else Update(Row,Ind,mid+1,R,r(node),val);
st[Row][node] = gcd2(st[Row][l(node)],st[Row][r(node)]);
}
ll query(int Row , int QL , int QR ,int L , int R, int node ){
// cout << "QUERY "<< L << " " << R << " node " << node << endl;
if( L > R || QL > R || QR < L )return 0;
if( L >= QL && R <= QR){
return st[Row][node];
}
int mid = (L+R)/2 ;
return gcd2(query(Row,QL,QR,L,mid,l(node)),query(Row,QL,QR,mid+1,R,r(node)));
}
void init(int R, int C) {
ROW = R;
COL = C;
}
void update(int P, int Q, long long K) {
/* ... */
Update(P,Q,0,COL-1,0,K);
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
ll ans = 0 ;
// cerr << "query*******"<<endl;
for(int i = P ; i <= U ; i++ ){
ll q = query(i,Q,V,0,COL-1,0);
// cout << "i " << i << "q "<<q<<endl;
ans = gcd2(q,ans);
}
return ans;
}
// int main(){
// int n , m , X ;
// cin >> n >> m >> X;
// init(n,m);
// for(int i = 0 ; i < X ; i++ ){
// int type ;
// cin >> type ;
// if( type == 1 ){
// int P, Q ; ll K ;
// cin >> P >> Q >> K ;
// update(P,Q,K);
// }else {
// int P,Q,U,V;
// cin >> P >> Q >> U >> V;
// cout << calculate(P,Q,U,V)<< " ";
// }
// }
// }
