#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long int n, q; vector <int> d; vector <pair <int, int> > a; int query(int t, int x){ int ret = 0; int pos = 0; for(auto &i : a){ int head = pos + t / i.first * i.first; if(head < x) break; ret += min(i.second, head - x + 1); pos -= i.second; } return ret; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> q; d.resize(n); for(auto &i : d) cin >> i; d.insert(d.begin(), 1); int prev = 1; for(auto &i : d){ int t = (i + prev - 1) / prev; if(prev > (int)1e9 / t) break; prev *= t; if(a.size() && prev == a.back().first) a.back().second++; else a.push_back(make_pair(prev, 1)); } while(q--){ int t, l, r; cin >> t >> l >> r; cout << query(t, l) - query(t, r + 1) << "\n"; } }