#include <bits/stdc++.h>

using namespace std;

const int N = 150'000 + 10,
					A = 1'000'000 + 10,
					S = 400;
int n, q;
int a[N];
struct Query { 
	int l, r, idx;
	friend istream& operator >> (istream& is, Query& rhs) { 
		return is >> rhs.l >> rhs.r;
	}
} query[N];

vector<int> pos[A];
vector<pair<int, int>> save[N];

int maxBlock[N / S], ma[N];
inline void upd(int i, int x) { 
	int block = (i - 1) / S + 1;
	maxBlock[block] = max(maxBlock[block], x);
	ma[i] = max(ma[i], x);
}
int que(int l, int r) { 
	int blockL = (l - 1) / S + 1, blockR = (r - 1) / S + 1;
	int ret = 0;
	if (blockL == blockR) { 
		for (int i = l; i <= r; ++i) ret = max(ret, ma[i]);
	} else { 
		for (int i = blockL + 1; i < blockR; ++i) ret = max(ret, maxBlock[i]);
		for (int i = l; i <= blockL * S - S + 1; ++i) ret = max(ret, ma[i]);
		for (int i = blockR * S + 1; i <= r; ++i) ret = max(ret, a[i]);
	}
	return ret;
}

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= q; ++i) cin >> query[i], query[i].idx = i;

	for (int i = 1; i <= n; ++i) pos[a[i]].push_back(i);

	for (int gcd = 1; gcd <= 1'000'000; ++gcd) { 
		vector<int> vt;
		for (int i = gcd; i <= 1'000'000; i += gcd) 
			vt.insert(vt.end(), pos[i].begin(), pos[i].end());
		if (vt.size() <= 2) continue;
		sort(vt.begin(), vt.end());

		vector<pair<int, int>> all;
		for (int i = 1; i < vt.size(); ++i) 
			all.push_back({vt[i - 1], 2 * vt[i] - vt[i - 1]});
		
		sort(all.begin(), all.end(), [&](const auto& a, const auto& b) { 
			return a.second < b.second;
		});

		int it = 0;
		for (const auto& [l, r] : all) { 
			while (it < vt.size() && vt[it] < r) it += 1;
			if (it == vt.size()) break; 
			save[l].push_back({gcd, vt[it]});
		}
	}

	sort(query + 1, query + q + 1, [&](const auto& a, const auto& b) { 
		return a.l > b.l;
	});

	vector<int> answer(q + 1);
	int it = n;
	for (int i = 1; i <= q; ++i) { 
		const auto& [l, r, idx] = query[i]; 

		while (it >= l) { 
			for (const auto& [value, r] : save[it]) upd(r, value);
			it -= 1;
		}

		answer[idx] = que(l, r);		
	}

	for (int i = 1; i <= q; ++i) cout << answer[i] << "\n";
}