卡常题，根号分治。卡了三页。
以下记\(V=\max\{a_i\}\)
考虑当\(k\le\sqrt V\)时，对于每一个\(k\)，写个ST表/线段树/分块即可，实测分块最快。复杂度分别为\(O(n\log n)+O(q)+O(n\log n)\qquad O(n)+O(q\log n)+O(n)\qquad O(n)+O(q\sqrt n)+O(n)\)。
当\(k>\sqrt{V}\)时，考虑\(a_i\bmod k\Leftrightarrow \min\{a_i-ck\}(c\in (\mathbb{N}\cup[0,\left\lfloor\frac{a_i}{k}\right\rfloor]))\)。考虑枚举\(c\)，发现这其实就是求区间非严格后继，求区间非严格后继，可以将序列降序，询问降序，每次询问前将所有大于询问的数插入，求区间min。
发现本题插入是\(O(n)\)的，询问是\(O(n\sqrt V)\)的，那么考虑如何将插入的时间复杂度变高，询问的复杂度变为\(O(1)\)以平衡复杂度。
\(O(1)\)查询的RMQ有两种：ST表和猫树（我太菜了，只会这两种，如果您还会其他的请接受我的膜拜）。但是这两东西都不支持快速动态插入。考虑将序列分块一下，然后用ST表或猫树维护每一块的最小值，然后散块用两个数组维护前缀最小值和后缀最小值即可。我用的是猫树。猫树插入时间复杂度是\(O(\frac{\sqrt{n}}{2}+\frac{\sqrt{n}}{4}+\cdots)=O(\sqrt{n})\)的，然后维护前后缀min的时间复杂度也是\(O(\sqrt n)\)的，所以总的复杂度是\(O(\sqrt n)\)的。
当询问\(l,r\)在同一块中时，直接暴力跑即可。
总的时间复杂度\(O(n\sqrt{V})\)的，但是常数比较大+时限太紧，严重卡常。
\(\color{#4f42b3}warning\):本篇代码不一定保证能过，但本人确实过了，写法较wang5，请谨慎食用。
卡常题，建议自行思考实现细节以及自身对代码常数的理解和优化。来自一篇题解
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(uint i = s;i <= t; i += p)
#define drep(i,s,t,p) for(uint i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
FILE *InFile = stdin,*OutFile = stdout;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
namespace IO{
struct IO{
char buf[1<<24],*p1,*p2;
char pbuf[1<<24], *pp;
#define gc() ((p1==p2&&(p2=((p1=buf)+fread(buf,1,1<<24,stdin)),p1==p2))?EOF:*p1++)
#define pc putchar_unlocked
template<class T>
inline void read(T &x){
x = 0;bool flag = false;char s = gc();
for(;s < '0' || '9' < s;s = gc());
for(;'0' <= s && s <= '9';s = gc()) x = (x<<1)+(x<<3)+(s^48);
}
template<class T,class ...Args>
inline void read(T &x,Args&... argc){read(x);read(argc...);}
inline void push(const char &c) {
if (pp - pbuf == 1<<24) fwrite(pbuf, 1, 1<<24, stdout), pp = pbuf;
*pp++ = c;
}
template <class T>
inline void write(T x) {
static T sta[35];
T top = 0;
do{
sta[top++] = x % 10, x /= 10;
}while(x);
while(top) push(sta[--top] + '0');
}
inline void write(char x){push(x);}
template <class T,class... Args>
inline void write(T x,Args... argc) {write(x);write(argc...);}
}io;
#define read io.read
#define write io.write
}using namespace IO;
const uint N = 3e5 + 10,V = 1e5 + 10,SN = 700;
#define eb emplace_back
#define pii pair<uint,uint>
#define mk make_pair
uint n,m,a[N],ans[N],mxn,spl,lg[N],st[20][N],md[N],siz;
uint len,L[SN],R[SN],pos[N],pre[SN][SN],suf[SN][SN],bn[SN];
pii b[N];vector<uint> have[V];
struct Q{uint l,r,id;Q(uint L,uint R,uint Id):l(L),r(R),id(Id){}};vector<Q> q[V];
inline void solve1(uint k){
rep(i,1,len,1) bn[i] = INT_MAX;
rep(i,1,len,1) rep(j,L[i],R[i],1) bn[i] = min(bn[i],md[j] = a[j]%k);
auto query = [](uint l,uint r){
uint p = pos[l],q = pos[r],res = INT_MAX;
if(p == q){rep(i,l,r,1) res = min(res,md[i]);return res;}
rep(i,l,R[p],1) res = min(res,md[i]);
rep(i,L[q],r,1) res = min(res,md[i]);
rep(i,p+1,q-1,1) res = min(res,bn[i]);
return res;
};
for(Q j:q[k]) ans[j.id] = query(j.l,j.r);
}
struct Cat_Tree{
uint f[20][10010],pos[N<<1],l[20010],r[20010];
uint len;
void build(uint k,uint L,uint R,uint dep){
l[k] = L,r[k] = R;
if(L == R) return pos[L] = k,void();
uint mid = (L + R) >> 1;
build(k<<1,L,mid,dep+1);build(k<<1|1,mid+1,R,dep+1);
f[dep][mid] = INT_MAX;
drep(i,mid-1,L,1) f[dep][i] = INT_MAX;
f[dep][mid+1] = INT_MAX;
rep(i,mid+2,R,1) f[dep][i] = INT_MAX;
}
inline void pre(uint n){
len = 2; while(len < n) len <<= 1;
build(1,1,len,1);
}
inline uint qry(uint l,uint r){
if(l > r) return INT_MAX;
if(l == r) return bn[l];
uint d = lg[pos[l]] - lg[pos[l]^pos[r]];
return min(f[d][l],f[d][r]);
}
inline void insert(uint val,uint pos,uint k,uint dep){
if(l[k] == r[k]) return;
uint mid = (l[k] + r[k]) >> 1;
if(pos <= mid){
insert(val,pos,k<<1,dep + 1);
f[dep][pos] = min(val,f[dep][pos]);
drep(i,pos-1,l[k],1) f[dep][i] = min(f[dep][i],f[dep][i + 1]);
}
else{
insert(val,pos,k<<1|1,dep + 1);
f[dep][pos] = min(val,f[dep][pos]);
rep(i,pos+1,r[k],1) f[dep][i] = min(f[dep][i],f[dep][i - 1]);
}
}
}cjs;
inline void Insert(uint val,uint P){
uint p = pos[P],bp = P - R[p-1];
pre[p][bp] = val;suf[p][bp] = val;
bn[p] = min(bn[p],val);
rep(i,bp+1,R[p]-L[p]+1,1) pre[p][i] = min(pre[p][i-1],pre[p][i]);
drep(i,bp-1,1,1) suf[p][i] = min(suf[p][i+1],suf[p][i]);
cjs.insert(bn[p],p,1,1);
}
inline uint qry(uint l,uint r){
uint p = pos[l],q = pos[r];
return min({suf[p][l-R[p-1]],pre[q][r-R[q-1]],cjs.qry(p+1,q-1)});
}
inline void solve2(){
cjs.pre(len);
sort(b+1,b+1+n,[](pii x,pii y){return x.first > y.first;});
uint p = 0;
rep(i,spl,mxn,1){
if(q[i].empty()) continue;
rep(j,i,mxn,i) have[j].eb(i);
}
drep(now,mxn,spl,1){
if(have[now].empty()) continue;
while(p < n && b[p + 1].first >= now) p++,Insert(b[p].first,b[p].second);
for(auto i:have[now]) for(auto j:q[i]) ans[j.id] = min(ans[j.id],qry(j.l,j.r)-now);
}
}
inline void solve(){
read(n,m);rep(i,1,n,1) read(a[i]),b[i] = mk(a[i],i);
rep(i,2,n,1) lg[i] = lg[i >> 1] + 1;
siz = sqrt(n),len = n/siz;
rep(i,1,len,1) L[i] = R[i-1] + 1,R[i] = i*siz;
if(R[len] < n) len++,L[len] = R[len-1] + 1,R[len] = n;
rep(i,1,len,1) rep(j,L[i],R[i],1) pos[j] = i;
memset(ans,0x3f,sizeof ans);memset(pre,0x3f,sizeof pre);
memset(suf,0x3f,sizeof suf);
mxn = *max_element(a+1,a+1+n);
uint t = lg[n];
rep(i,1,n,1) st[0][i] = a[i];
rep(j,1,t,1) rep(i,1,n-(1<<j)+1,1) st[j][i] = min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
auto query = [](uint l,uint r){uint k = lg[r-l+1];return min(st[k][l],st[k][r-(1<<k)+1]);};
rep(i,1,m,1){
uint l,r,k;read(l,r,k);
if(pos[l] == pos[r]){
uint res = INT_MAX;
rep(j,l,r,1) res = min(res,a[j]%k);
ans[i] = res;continue;
}
q[k].eb(Q(l,r,i));ans[i] = query(l,r);
}
spl = 475;
rep(i,1,spl,1) if(q[i].size()) solve1(i);
memset(bn,0x3f,sizeof bn);
spl++;solve2();
rep(i,1,m,1) cout<<ans[i]<<'\n';
}
signed main(){solve();}