#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const ll mxn = 5e5+10;
ll arr[mxn];
ll N,Q;
vector<pair<ll,pll>> v;
vector<pll> calc(ll t){
vector<pll> re = {pll(t,t)};
ll now = t-1;
for(auto [step,r]:v){
if(now<=0)break;
//cerr<<t<<":"<<i.fs<<','<<i.sc<<"::"<<now<<','<<now/arr[i.fs]*arr[i.fs]-i.sc+i.fs-1<<endl;
now = -r.fs+(now+r.fs)/step*step;
if(now<=0)break;
re.push_back(pll(now-(r.sc-r.fs),now));
now = re.back().fs-1;
}
reverse(re.begin(),re.end());
//cerr<<t<<":";for(auto &i:re)cerr<<i.fs<<' '<<i.sc<<',';cerr<<endl;
return re;
}
void solve(){
ll t,l,r;
cin>>t>>l>>r;
auto vv = calc(t);
ll ans = 0;
//for(auto &i:vv)cerr<<i.fs<<' '<<i.sc<<',';cerr<<endl;
for(auto &i:vv){
if(i.sc<l||i.fs>r)continue;
ans += min(i.sc,r)-max(l-1,i.fs-1);
}
cout<<ans<<'\n';
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>Q;
ll d = 0;
for(int i = 1;i<=N;i++){
cin>>arr[i];
if(v.empty())d = arr[i],v.push_back(make_pair(arr[i],pll(i,i)));
else if(arr[v.back().fs]>arr[i])v.back().sc.sc = i;
else if(d<arr[i]){
d = (arr[i]+d-1)/d*d;
v.push_back(make_pair(d,pll(i,i)));
}
else v.back().sc.sc = i;
//cout<<i<<":"<<d<<endl;
}
//for(auto &i:v)cout<<i.fs<<','<<i.sc<<":"<<arr[i.fs]<<endl;
while(Q--)solve();
}
