#include <bits/stdc++.h>
using namespace std;

const int MX = 1e5 + 10;
typedef pair<int,int> pii;
vector<int> Arr, prime[MX], tmp[MX];
int start[MX], fin[MX], val[MX];
pii tree[MX * 10];

void sieve(){
	for(int i = 2; i<MX; i++){
		if(!prime[i].size()){
			for(int j = i; j<MX; j += i){
				prime[j].push_back(i);
			}
		}
	}
}

void build(int node, int st, int en){
	if(st == en){ 
		tree[node] = pii(val[Arr[st]], 1); 
	    return;
	}
	int l = 2*node, r = l + 1, mid = (st + en)/2;
	build(l, st, mid);
	build(r, mid + 1, en);
	if(tree[l].first > tree[r].first) tree[node] = tree[l];
	else if(tree[r].first > tree[l].first) tree[node] = tree[r];
	else{ 
	  tree[node] = tree[l];
	  tree[node].second += tree[r].second;
	}
}

pii query(int node, int st, int en, int i, int j){
    if(st > j || en < i) return pii(-1, -1);
    if(st >= i && en <= j) return tree[node];
    int l = 2*node, r = l + 1, mid = (st + en)/2;
    pii p = query(l, st, mid, i, j);
    pii q = query(r, mid + 1, en, i, j);
    if(p.first == -1) return q;
    if(q.first == -1) return p;
    
    if(p.first > q.first) return p;
    if(q.first > p.first) return q;
    
    return pii(p.first, p.second + q.second);
}

int main() {
	int n, m, num, a, b;
	sieve();
	scanf("%d %d", &n, &m);
	memset(start, 0, sizeof(start));
	memset(fin, 0, sizeof(fin));
	memset(val, 0, sizeof(val));
	set<int> S;
	
	for(int i = 1; i<=n; i++){
		scanf("%d", &num);
		val[i - 1] = num;
		int sz = prime[num].size();
		
		for(int j = 0; j<sz; j++){
			int id = prime[num][j];
			S.insert(id);
			tmp[id].push_back(i - 1);
		}
	}
	
	set<int>:: iterator it;
	int st = 0;
	for(it = S.begin(); it != S.end(); it++){
		num = (*it);
		int sz = tmp[num].size();
		start[num] = st;
		fin[num] = st + sz - 1;
		st += sz;
			
		for(int i = 0; i<sz; i++){
			int id = tmp[num][i];
			Arr.push_back(id);
		}
			
	}
	
	build(1, 0, Arr.size() - 1);
	for(int i = 1; i<=m; i++){
		int ans = -1, cnt = -1;
		scanf("%d %d %d", &num, &a, &b); a--, b--;
		
		int sz = prime[num].size();
		for(int j = 0; j<sz; j++){
			int id = prime[num][j];
			int st = start[id], en = fin[id];
			if(st == 0 && en == 0) continue;
			int l = lower_bound(Arr.begin() + st, Arr.begin() + en + 1, a) - Arr.begin();
			int r = upper_bound(Arr.begin() + st, Arr.begin() + en + 1, b) - Arr.begin();
			r--;
			if(l > r) continue;
			pii p = query(1, 0, Arr.size() - 1, l, r);
			if(p.first > ans){
				ans = p.first;
				cnt = p.second;
			}
		}
		
		printf("%d %d\n", ans, cnt);
	}
	return 0;
}