#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define NLIMIT 100000
#define MLIMIT 100000
#define ALIMIT 100000

#define N 100100
#define F 350

void assert(bool f) { if(!f) { int a = 10; printf("%d\n", 10/a); } }
struct node {
	int x,y,z,g;
	bool operator <(const node &o) const {
		return y < o.y;
	}
};

int small_primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349};
int a[N], st[70][N*5] = {0}, countt[70][N*5], last_seen[N], q[N*5], qcountt[N*5], answer[N], canswer[N];
vector <int> list[N];
node b[N];

//Sets the value at x to y in z'th segment tree
void update(int cur, int s, int e, const int x, const int y, const int z) {
	if(s == e-1) {
		st[z][cur] = y;
		countt[z][cur] = 1;
		return;
	}
	int m = (s+e)>>1, c1 = cur<<1, c2 = c1 | 1;
	if(x < m) update(c1, s, m, x, y, z);
	else update(c2, m, e, x, y, z);
	if(st[z][c1] > st[z][c2]) st[z][cur] = st[z][c1], countt[z][cur] = countt[z][c1];
	else if(st[z][c1] < st[z][c2]) st[z][cur] = st[z][c2], countt[z][cur] = countt[z][c2];
	else st[z][cur] = st[z][c1], countt[z][cur] = countt[z][c1] + countt[z][c2];
}

//Returns the maximum value in range [S, E) in z'th segment tree
void query(int cur, int s, int e, const int S, const int E, const int z) {
	if(e <= S || s >= E) {
		q[cur] = 0;
		qcountt[cur] = 0;
		return;
	}
	if(s >= S && e <= E) {
		q[cur] = st[z][cur];
		qcountt[cur] = countt[z][cur];
		return;
	}
	int m = (s+e)>>1, c1 = cur<<1, c2 = c1 | 1;
	query(c1, s, m, S, E, z);
	query(c2, m, e, S, E, z);
	if(q[c1] > q[c2]) q[cur] = q[c1], qcountt[cur] = qcountt[c1];
	else if(q[c1] < q[c2]) q[cur] = q[c2], qcountt[cur] = qcountt[c2];
	else q[cur] = q[c1], qcountt[cur] = qcountt[c1] + qcountt[c2];
}

int main() {
	for(int i=0; i<N; i++) last_seen[i] = -1;

	int n, m;
	scanf("%d%d", &n, &m);
														assert( 1 <= n && n <= NLIMIT );
														assert( 1 <= m && m <= MLIMIT );
	for(int i=0; i<n; i++) {							// O(N)
		scanf("%d", &a[i]);
	}
	for(int i=0; i<m; i++) {							// O(M)
		scanf("%d%d%d", &b[i].g, &b[i].x, &b[i].y);
														assert( 1 <= b[i].g && b[i].g <= ALIMIT );
														assert( 1 <= b[i].x && b[i].x <= n );
														assert( b[i].x <= b[i].y && b[i].y <= n);
		b[i].x--; b[i].y--;
		b[i].z = i;
	}
	
	sort(b, b+m);										// O(M * Log M)
	//Sort them on y.

	int cur, cury = -1, ans, cans;
	for(int i=0; i<m; i++) {							// O(M)
		while(cury < b[i].y) {							// O(N)
			cur = a[++cury];
			for(int j=0; j<70; j++) {					// O(N * 70)
				if(cur % small_primes[j] == 0) {		// Passes if atmost O(N * 7)
					//Enters if small_primes[j] is present in cur.
					//Then update the j'th segment tree at position cury to value a[cury]
					update(1, 0, n, cury, a[cury], j);	// O(N * 7 * Log N)
					while(cur % small_primes[j] == 0)
						cur /= small_primes[j];
				}
			}
			//Update the latest seen timestamp, we use this later
			last_seen[a[cury]] = cury;
			//Also push them into a list, we need this for binary search later
			list[a[cury]].push_back(cury);
		}
		cur = b[i].g;
		ans = 0;
		for(int j=0; j<70; j++) {						// O(M * 70)
			if(cur % small_primes[j] == 0) {			// Passes if atmost O(M * 7)
				//Enters if small_primes[j] is present in cur.
				//Then query the j'th segment tree in range b[i].x to b[i].y
				query(1, 0, n, b[i].x, b[i].y+1, j);	// O(M * 7 * Log M)
				if(q[1] > ans) //Update answer if greater value
					ans = q[1], cans = qcountt[1];
				while(cur % small_primes[j] == 0)
					cur /= small_primes[j];
			}
		}
		if(cur > 1) {
			//Special case for one prime number which is > 350
			int mcur = cur * 300;
			while(mcur > N) mcur -= cur;
			while( mcur >= cur && mcur > ans ) {		// O(M * 300)
				if(last_seen[mcur] >= b[i].x) {			// Passes only once
					//last_seen[mcur] is atleast as much as b[i].x, that is the left index.
					//So mcur is a valid candidate
					ans = mcur;
					int tempa = -1, add = (1<<20), tempb;
					while(add) {						// O(M * 20)
						//Binary search to count the number of occurrances
						tempb = tempa + add;
						add >>= 1;
						if(tempb >= list[mcur].size()) continue;
						if(list[mcur][tempb] < b[i].x) tempa = tempb;
					}
					cans = list[mcur].size() - (tempa + 1);
					break;
				}
				mcur -= cur;
			}
		}
		if(ans == 0) ans = -1, cans = -1;
		answer[b[i].z] = ans;
		canswer[b[i].z] = cans;
	}
	for(int i=0; i<m; i++) printf("%d %d\n", answer[i], canswer[i]);
	return 0;
}