#include<bits/stdc++.h> #define endl '\n' using namespace std; const int maxn=1e5; const int B=1000; int n,m; int BC; int L[107],R[107],bel[maxn+7]; int Ans[107][maxn+7]; int buc[maxn+7]; int a[maxn+7],V; inline void Init(){ for(int i=1;i<=n;i++)bel[i]=(i-1)/B+1,V=max(V,a[i]); BC=bel[n]; for(int i=1;i<=BC;i++){ L[i]=R[i-1]+1; R[i]=i*B; } R[BC]=n; for(int i=1;i<=BC;i++){ memset(buc,0,sizeof(buc)); for(int j=L[i];j<=R[i];j++)buc[a[j]]=a[j]; for(int j=1;j<=V;j++)buc[j]=max(buc[j],buc[j-1]); for(int k=1;k<=maxn;k++)for(int j=0;j<=V;j+=k)Ans[i][k]=max(Ans[i][k],buc[min(j+k-1,V)]-j); } } inline int Qry(int l,int r,int k){ int BL=bel[l],BR=bel[r]; int ret=0; if(BL==BR){ for(int i=l;i<=r;i++)ret=max(ret,a[i]%k); return ret; } for(int i=l;i<=R[BL];i++)ret=max(ret,a[i]%k); for(int i=L[BR];i<=r;i++)ret=max(ret,a[i]%k); for(int i=BL+1;i<=BR-1;i++)ret=max(ret,Ans[i][k]); return ret; } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifndef ONLINE_JUDGE freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); #endif cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; Init(); while(m--){ int l,r,k; cin>>l>>r>>k; cout<<Qry(l,r,k)<<endl; } cout.flush(); return 0; }