Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
- char _;
- #define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
- #define all(a) a.begin(),a.end()
- #define println printf("\n");
- #define readln(x) getline(cin,x);
- #define pb push_back
- #define endl "\n"
- #define INT_INF 0x3f3f3f3f
- #define LL_INF 0x3f3f3f3f3f3f3f3f
- #define MOD 1000000007
- #define MOD2 1494318097
- #define SEED 131
- #define mp make_pair
- #define fastio cin.tie(0); cin.sync_with_stdio(0);
- #define MAXP 205
- #define MAXN 100005
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef unordered_map<int,int> umii;
- typedef pair<int,int> pii;
- typedef pair<double,double> pdd;
- typedef pair<ll,ll> pll;
- typedef pair<int,pii> triple;
- typedef int8_t byte;
- mt19937 g1(chrono::steady_clock::now().time_since_epoch().count());
- int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
- ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}
- ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
- ll lcm(ll a, ll b){return a*b/gcd(a,b);}
- ll fpow(ll b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
- ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
- int sz,num_q,R[MAXN],C[MAXN];
- int rows[MAXP][MAXN],cols[MAXP][MAXN];
- vector<int> v;
- inline bool isp(int n){
- for(int i=2; i<=sqrt(n); i++)
- if(n%i == 0)
- return false;
- return true;
- }
- inline int maxpr(int row, int c1, int c2){
- int ans = -1;
- for(int i=0; i<v.size(); i++){
- if(R[row]%v[i] == 0) ans = v[i];
- if(cols[i][c2]-cols[i][c1-1] == c2-c1+1) ans = v[i];
- }
- return ans;
- }
- inline int maxpc(int col, int r1, int r2){
- int ans = -1;
- for(int i=0; i<v.size(); i++){
- if(C[col]%v[i] == 0) ans = v[i];
- if(rows[i][r2]-rows[i][r1-1] == r2-r1+1) ans = v[i];
- }
- return ans;
- }
- int main(){
- scanf("%d %d",&sz,&num_q);
- for(int i=2; i<=1000; i++)
- if(isp(i)) v.pb(i);
- for(int i=1; i<=sz; i++)
- scanf(" %d",&R[i]);
- for(int i=1; i<=sz; i++)
- scanf(" %d",&C[i]);
- for(int i=0; i<v.size(); i++){
- for(int k=1; k<=sz; k++){
- rows[i][k] = rows[i][k-1];
- cols[i][k] = cols[i][k-1];
- if(R[k]%v[i] == 0) rows[i][k]++;
- if(C[k]%v[i] == 0) cols[i][k]++;
- }
- }
- while(num_q--){
- int r1,c1,r2,c2; scanf(" %d %d %d %d",&r1,&c1,&r2,&c2);
- if(r1 == r2) printf("%d\n",maxpr(r1,c1,c2));
- else if(c1 == c2) printf("%d\n",maxpc(c1,r1,r2));
- else{
- int ans = -1;
- for(int i=0; i<v.size(); i++){
- if(R[r1]%v[i] == 0 && R[r2]%v[i] == 0 && cols[i][c2]-cols[i][c1-1]) ans = v[i];
- if(C[c1]%v[i] == 0 && C[c2]%v[i] == 0 && rows[i][r2]-rows[i][r1-1]) ans = v[i];
- if(C[c2]%v[i] == 0 && R[r1]%v[i] == 0) ans = v[i];
- if(C[c1]%v[i] == 0 && R[r2]%v[i] == 0) ans = v[i];
- if(cols[i][c2]-cols[i][c1-1] == c2-c1+1) ans = v[i];
- if(rows[i][r2]-rows[i][r1-1] == r2-r1+1) ans = v[i];
- }
- printf("%d\n",ans);
- }
- }
- }
- /*
- 3 1
- 2 2 2
- 3 3 3
- 1 1 3 3
- ans=3
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement