#include <bits/stdc++.h>
#include <stdio.h>
#include "game.h"
#define max_N 100001
long long gcd2(long long X, long long Y) {
//printf("X\n");
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
long long mat[1000][1000];
long long st[10][max_N * 4];
int sa, su, sub;
void init(int R, int C) {
sa = R;
su = C;
if(R > 10) sub = 1;
else sub = 3;
}
void guncelle(int dugum, int sol, int sag, int satir, int sutun, long long K) {
if (sol == sag) {
st[satir][dugum] = K;
return;
}
int orta = (sol + sag) / 2;
if (orta >= sutun)
guncelle(dugum*2, sol, orta, satir, sutun, K);
else
guncelle(dugum*2+1, orta+1, sag, satir, sutun, K);
st[satir][dugum] = gcd2(st[satir][dugum*2], st[satir][dugum*2+1]);
}
void update(int P, int Q, long long K) {
if (sub == 3)guncelle(1, 0, su-1, P, Q, K);
else mat[P][Q] = K;
}
long long sorgu(int dugum, int sol, int sag, int satir, int aSol, int aSag) {
// printf("Dugum: %d, sol: %d, sag: %d, satir: %d, aSol: %d, aSag: %d\n", dugum, sol, sag, satir, aSol, aSag);
if(sol > aSag || sag < aSol)
return -1;
if(sol >= aSol && sag <= aSag)
return st[satir][dugum];
int orta = (sol + sag) / 2;
long long s1 = sorgu(dugum*2, sol, orta, satir, aSol, aSag);
long long s2 = sorgu(dugum*2+1, orta+1, sag, satir, aSol, aSag);
if ( (s1 != -1) && (-1 != s2) )
return gcd2(s1, s2);
if (s1 == -1)
return s2;
return s1;
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
if (sub == 3){
long long ekok = sorgu(1, 0, su-1, P, Q, V);
for (int i = P+1; i <= U; i++) {
long long s = sorgu(1, 0, su-1, i, Q, V);
ekok = gcd2(ekok, s);
}
return ekok;
}
else {
long long ekok;// = mat[P][Q];
for(int i = P; i <= U; i++) {
for(int j = Q; j <= V; j++)
ekok = gcd2(ekok, mat[i][j]);
}
return ekok;
}
}
