#include<bits/stdc++.h>
	using namespace std;
	#define ll long long  
	#define endl '\n'
	const int N = 1e6+5;
	vector<int>g[N];
	vector<pair<int,int>>fk[N], ask[N];
	int a[N], ans[N];
	int tr[N];
	
	void add(int x, int y){
		for(;x; x-=(x&-x)){
			tr[x] = max(tr[x], y);
		}
	}
	int cal(int x){
		int y = -1;
		for(;x<=200000; x+=(x&-x)){
			y = max(y, tr[x]);
		}
		return y;
	} 
	
	
	signed main (){
		std::ios::sync_with_stdio(false);  
		cin.tie(NULL); 
		cout.tie(NULL);
		memset(tr, -1, sizeof(tr));
		int n, q; cin >> n >> q;
		vector<int>fac;
		for(int i=1; i<=n; i++){
			cin >> a[i];
			for(int j = 1; j*j <= a[i]; j++)if(a[i]%j == 0){
				g[j].push_back(i);
				if(j*j != a[i]) g[a[i]/j].push_back(i);
			}
		}
		const int M = 1e6;
		vector<array<int,3>>edg;
		// map<<pair<int,int>>,int>mp;
		
		for(int i=1; i<=M; i++)if(g[i].size() >= 3){
			int pos = 2;
			for(int j = 0; j+2 < g[i].size(); j++){
				pos = max(pos, j+2);
				int l = g[i][j];
				int m = g[i][j+1];
				while(g[i][pos] - m < m - l){
					pos++;
					if(pos >= g[i].size())break;
				}
				if(pos >= g[i].size())break;
				int r = g[i][pos];
				fk[r].push_back({l, i});
			}
		}
		
		// for(int i=1; i<=M; i++)if(g[i].size() >= 3){
			// int pos = 3;
			// for(int j = 0; j+2 < g[i].size(); j++){
				// int l = g[i][j];
				// int m = g[i][j+1];
				// int pos = lower_bound(g[i].begin(), g[i].end(), 2*m-l) - g[i].begin();
				// if(pos >= g[i].size())break;
				// int r = g[i][pos];
				// fk[r].push_back({l, i});
			// }
		// }
		for(int i=1; i<=n; i++){
			int l, r; cin >> l >> r;
			ask[r].push_back({l, i});
		}
		for(int i=1; i<=n; i++){
			for(auto [pos, val]: fk[i]){
				// cout << i << ' ' << pos << ' ' << val << endl;
				//pos~n
				add(pos, val);
			}
			for(auto [pos, id]: ask[i]){
				ans[id] = cal(pos);
			}
		}
		for(int i=1; i<=n; i++) cout << ans[i] << endl;
	
		
	
	}