#include<bits/stdc++.h> using namespace std; int n,m; void read(int &x){ x=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar(); } int a[100005]; int l[100005],r[100005],bel[100005],mx[300][100005],tot,cnt[100005],lst[100005]; const int B=400; int qu(int L,int R,int k){ if(bel[L]==bel[R]){ // cout<<L<<" "<<R<<" "<<k<<endl; int res=0; for(int i=L;i<=R;i++){ res=max(a[i]%k,res); } return res; } int res=0; for(int i=L;i<=r[bel[L]];i++)res=max(res,a[i]%k); for(int i=l[bel[R]];i<=R;i++)res=max(res,a[i]%k); for(int i=bel[L]+1;i<bel[R];i++)res=max(res,mx[i][k]); return res; } int main(){ //freopen("slpjbh.in","r",stdin); //freopen("slpjbh.out","w",stdout); read(n),read(m); for(int i=1;i<=n;i++)read(a[i]); for(int i=1;i<=n/B;i++){ l[i]=(i-1)*B+1,r[i]=i*B; } tot=n/B; if(n%B)tot++,l[tot]=n/B*B+1,r[tot]=n; for(int i=1;i<=n;i++){ bel[i]=i/B+1; } for(int i=1;i<=tot;i++){ for(int j=1;j<=1e5;j++)cnt[j]=0; for(int j=l[i];j<=r[i];j++)cnt[a[j]]=1; for(int j=1;j<=1e5;j++)lst[j]=cnt[j]?j:lst[j-1]; for(int j=1;j<=1e5;j++){ for(int k=j;k<=1e5;k+=j){ mx[i][j]=max(mx[i][j],lst[k-1]-k+j); } } } // cout<<mx[1][1]<<" "<<mx[1][2]<<" "<<mx[1][3]<<" "<<mx[1][4]<<" "<<mx[1][5]<<" "<<mx[1][6]<<endl;/ int L,R,k; while(m--){ read(L),read(R),read(k); printf("%d\n",qu(L,R,k)); } return 0; }