我们不妨来考虑所有询问都是 \(l=1,r=n\) 的情形，这种情况下需要对每个值处理出他经过一系列变换后变成了什么数。
考虑用 \(\text{solve}(p,l,r)\) 表示我们现在要计算 \(x\in[l,r]\) 的这些数在经过 \(x\leftarrow |x-a_p|,x\leftarrow |x-a_{p+1}|\)，一直到 \(x\leftarrow |x-a_n|\) 这些 \(n-p+1\) 个变换后会变成什么数。分类讨论一下：
- 若 \(l\le a_p\le r\)，我们找到 \([l,a_p],[a_p+1,r]\) 中较长的一段，那么较短的一段可以完全由较长的一段推出，因此我们可以舍弃较短的一段，然后继续向 \(p+1\) 递归。
- 若 \(a_p<l\)，那么可以转到 \(\text{solve}(p+1,l-a_p,r-a_p)\)，然后相当于要把传回来的这个序列平移到 \([l,r]\) 的范围内。
- 若 \(a_p>r\)，类似地也可以转到 \(\text{solve}(p+1,a_p-r,a_p-l)\)，然后翻转一下再平移到 \([l,r]\) 的范围内。
实现的时候可以用 \(\text{solve}(p,l,r,lp,d,\Delta)\) 表示把 \([l,r]\) 的答案填到 \(\text{ans}[lp\cdots lp+\Delta\times d-1]\) 上，\(\Delta=-1\) 则表示反着填。
解决了这个问题之后，区间查询也是简单的：把序列分成 \(B\) 块，对第 \(i\) 块预处理 \([0,V]\) 每个数填进去的答案 \(f(i,j)\)，查询的时候先暴力跳散块，再利用 \(f\) 数组快速跳过整块。这样复杂度是 \(O(BV+\frac{nm}{B}+nB)\)，不妨设 \(n,m\) 同阶，那么取 \(B=\frac{n}{\sqrt{V}}\) 就有复杂度 \(O(n\sqrt{V})\)，空间复杂度也是 \(O(n\sqrt{V})\)。
由于散块暴力跳的过程实际上很快，实际实现的时候可能块长需要取大一点，也就是 \(B\) 取小一点。
//-DYUNQIAN -std=c++14 -O2 -Wall
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
const int N=1e5+5;
const int V=1e7;
const int B=75;
int ans[B+5][V+5],a[N],n,m,L[B+5],R[B+5],bl[N];
void solve(int id,int p,int tar,int l,int r,int st,int len,int d){
if(p==tar+1){
int p=st;
for(int i=l;i<=r;i++)ans[id][p]=i,p+=d;
return ;
}
if(a[p]<l){solve(id,p+1,tar,l-a[p],r-a[p],st,len,d);return ;}
if(a[p]>r){solve(id,p+1,tar,a[p]-r,a[p]-l,st+(len-1)*d,len,-d);return ;}
int Lp=a[p]-l,Rp=r-a[p];int pos=st+(a[p]-l)*d;
if(Lp>Rp){
solve(id,p+1,tar,0,a[p]-l,pos,Lp+1,-d);
//[ pos , pos-(Lp+1)*d ]
for(int i=1;i<=Rp;i++)ans[id][pos+i*d]=ans[id][pos-i*d];
//[ pos+d , pos+Rp*d ]
}
else{
solve(id,p+1,tar,0,r-a[p],pos,Rp+1,d);
for(int i=1;i<=Lp;i++)ans[id][pos-i*d]=ans[id][pos+i*d];
}
}
int query(int l,int r,int v){
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++)v=abs(v-a[i]);
return v;
}
for(int i=l;i<=R[bl[l]];i++)v=abs(v-a[i]);
for(int i=bl[l]+1;i<=bl[r]-1;i++)v=ans[i][v];
for(int i=L[bl[r]];i<=r;i++)v=abs(v-a[i]);
return v;
}
signed main(void){
n=read(),m=read();int lans=0;
for(int i=1;i<=n;i++)a[i]=read();
int S=(int)(n/B)+10;
memset(L,63,sizeof(L));
for(int i=1;i<=n;i++)bl[i]=(i-1)/S+1,L[bl[i]]=min(L[bl[i]],i),R[bl[i]]=i;
for(int i=1;i<=bl[n];i++)solve(i,L[i],R[i],0,V,0,V+1,1);
for(int i=1;i<=m;i++){
int l=read(),r=read(),v=read();
l^=lans,r^=lans,v^=lans;
cout<<(lans=query(l,r,v))<<'\n';
}
return 0;
}