#include <bits/stdc++.h> using namespace std; #define endl "\n" // #define int long long int bel[100300],L[100300],R[100300]; const int B=300; int n,q; int a[100030]; int mx[3010][510]; int k[100030]; struct ask{ int l,r,w,id; }; vector<ask>A[100300]; vector<int>g[100300]; int ANS[100300]; int w[100300<<2]; #define lc(x) (x<<1) #define rc(x) (x<<1|1) inline void upd(int x){ w[x]=max(w[lc(x)],w[rc(x)]); } inline void mod(int x,int l,int r,int c,int k){ if(l==r){ w[x]=k; return ; } int mid=l+r>>1; if(c<=mid)mod(lc(x),l,mid,c,k); else mod(rc(x),mid+1,r,c,k); upd(x); } inline int gt(int x,int l,int r,int L,int R){ if(L<=l&&r<=R)return w[x]; int mid=l+r>>1; int res=0; if(L<=mid)res=max(res,gt(lc(x),l,mid,L,R)); if(R>mid)res=max(res,gt(rc(x),mid+1,r,L,R)); return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++){ cin>>a[i]; bel[i]=(i+B-1)/B; if(!L[bel[i]])L[bel[i]]=i; R[bel[i]]=i; g[a[i]].push_back(i); } for(int i=1;i<=1500;i++) for(int j=1;j<=bel[n];j++) for(int k=L[j];k<=R[j];k++) mx[i][j]=max(mx[i][j],a[k]%i); for(int i=1;i<=q;i++){ int l,r; cin>>l>>r>>k[i]; if(k[i]<=1500){ int res=0; if(bel[l]==bel[r]) for(int j=l;j<=r;j++) res=max(res,a[j]%k[i]); else{ for(int j=l;j<=R[bel[l]];j++) res=max(res,a[j]%k[i]); for(int j=L[bel[r]];j<=r;j++) res=max(res,a[j]%k[i]); for(int j=bel[l]+1;j<=bel[r]-1;j++) res=max(res,mx[k[i]][j]); } ANS[i]=res; } else{ for(int j=k[i];j<=2e5;j+=k[i]){ if(i<=1e5) A[j].push_back({l,r,j,i}); else{ A[j].push_back({l,r,j,i}); break; } } } } for(int i=1;i<=1e5+1;i++){ for(auto a:A[i]){ int l=a.l,r=a.r,id=a.id,w=a.w; // int w=gt(1,1,n,l,r); ANS[id]=max(ANS[id],k[id]-(w-gt(1,1,n,l,r))); } for(int x:g[i]) mod(1,1,n,x,i); } for(int i=1;i<=q;i++) cout<<ANS[i]<<endl; return 0; }