#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <cstring>
#include <fstream>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
bool is_prime[maxn];

vector<int> idx[1000004];
int x[maxn];
vector<int> prime;
int main() {
//    ifstream cin("in.txt");
    ios_base::sync_with_stdio(false);
    memset(is_prime, true, sizeof is_prime);
    is_prime[0] = false;
    is_prime[1] = false;

    int cnt = 0;

    int ma = 0;
    for(ll i = 2; i <= maxn; i++) {
        if(is_prime[i]) {
            prime.push_back(i);
            for(ll j = i * i; j <= maxn; j += i) {
                is_prime[j] = false;
            }
        }
    }
    int n,m;
    cin>>n>>m;

    for(int i=0;i<n;i++){
        cin>>x[i];

        int sq = sqrt(x[i]);
        for(int j = 1; j <= sq; j++) {
            if(x[i] % j == 0) {
                if(is_prime[j]) {
                    idx[j].push_back(i);
                }

                if(j != x[i] / j and is_prime[x[i] / j]) {
                    idx[x[i] / j].push_back(i);
                }
            }
        }

    }

    int sz = (int) prime.size();
    for(int i=0;i<m;i++){
        int l,r,u;
        cin>>l>>r>>u;
        l--; r--;

        int j = (int) (lower_bound(prime.begin(), prime.end(), u) - prime.begin());

        int res = 2e9;
        if(j >= 0 and j < sz) {
            int lj = j, rj = j;

            bool ok = false;
            while(lj >= 0 and rj < n) {
                int p = prime[lj];

                vector<int>::iterator it = lower_bound(idx[p].begin(), idx[p].end(), l);
                if(it != idx[p].end() and *it <= r) {
                    res = min(res, abs(p - u));
                    ok = true;
                }

                p = prime[rj];
                it = lower_bound(idx[p].begin(), idx[p].end(), l);
                if(it != idx[p].end() and *it <= r) {
                    res = min(res, abs(p - u));
                    ok = true;
                }

                if(ok) {
                    break;
                }
                lj--;
                rj++;

            }


            while(lj >= 0 ) {
                int p = prime[lj];

                vector<int>::iterator it = lower_bound(idx[p].begin(), idx[p].end(), l);
                if(it != idx[p].end() and *it <= r) {
                    res = min(res, abs(p - u));
                    ok = true;
                }


                if(ok) {
                    break;
                }
                lj--;

            }
            while(rj < n ) {
                int p = prime[rj];

                vector<int>::iterator it = lower_bound(idx[p].begin(), idx[p].end(), l);
                if(it != idx[p].end() and *it <= r) {
                    res = min(res, abs(p - u));
                    ok = true;
                }


                if(ok) {
                    break;
                }
                rj++;

            }
            cout << res << " ";
        }


    }


    return 0;
}