#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; void solve(){ int n, L; cin >> n >> L; vector<int> a(n+1); for(int i = 1; i <= n; i++){ cin >> a[i]; } sort(a.begin()+1, a.end()); a[0] = -1e9; vector<pair<int, int>> b(1); int k = 0; for(int i = 1; i <= n; i++){ if(a[i] == a[i-1]){ b[k].second++; }else{ k++; b.push_back({a[i], 1}); } } b[0] = b[1]; int B = 1000; if((int)b.size() > B){ int Q; cin >> Q; for(int i = 1; i <= Q; i++){ int s, t, T; cin >> s >> t >> T; cout << "No\n"; } return; } auto chmin = [&](ll &a, ll b) -> void{ a = min(a, b); }; n = b.size()-1; b.push_back(b[n]); vector<int> pfcnt(n+1, 0); for(int i = 1; i <= n; i++){ pfcnt[i] = pfcnt[i-1] + b[i].second; } //f[i][j] : min cost to cover [1, i] and [j, n], if i < or > j means standing at i //answer at i will be f[i][i+1] vector<vector<ll>> f(n+2, vector<ll>(n+2, INF)); f[0][n+1] = 0; for(int len = n+2; len >= 3; len--){ for(int i = 0; i <= n; i++){ int j = i+len-1; if(j > n+1) continue; //standing at i { ll c = pfcnt[i] + pfcnt[n]-pfcnt[j-1]; if(i+1 <= n){ ll di = b[i+1].first - b[i].first; chmin(f[i+1][j], f[i][j] + (c+1)*di + b[i+1].second); } if(j-1 >= 1){ ll dj = b[j-1].first - b[i].first; chmin(f[j-1][i], f[i][j] + (c+1)*dj + b[j-1].second); } } //standing at j { ll c = pfcnt[i] + pfcnt[n]-pfcnt[j-1]; if(i+1 <= n){ ll di = b[j].first - b[i+1].first; chmin(f[i+1][j], f[j][i] + (c+1)*di + b[i+1].second); } if(j-1 >= 1){ ll dj = b[j].first - b[j-1].first; chmin(f[j-1][i], f[j][i] + (c+1)*dj + b[j-1].second); } } //yay! } } //holy shit case handling //g is f but starting at n vector<vector<ll>> g(n+2, vector<ll>(n+2, INF)); g[n+1][0] = 0; for(int len = n+2; len >= 3; len--){ for(int i = 0; i <= n; i++){ int j = i+len-1; if(j > n+1) continue; //standing at i { ll c = pfcnt[i] + pfcnt[n]-pfcnt[j-1]; if(i+1 <= n){ ll di = b[i+1].first - b[i].first; chmin(g[i+1][j], g[i][j] + (c+1)*di + b[i+1].second); } if(j-1 >= 1){ ll dj = b[j-1].first - b[i].first; chmin(g[j-1][i], g[i][j] + (c+1)*dj + b[j-1].second); } } //standing at j { ll c = pfcnt[i] + pfcnt[n]-pfcnt[j-1]; if(i+1 <= n){ ll di = b[j].first - b[i+1].first; chmin(g[i+1][j], g[j][i] + (c+1)*di + b[i+1].second); } if(j-1 >= 1){ ll dj = b[j].first - b[j-1].first; chmin(g[j-1][i], g[j][i] + (c+1)*dj + b[j-1].second); } } //yay! } } b.pop_back(); b.push_back({1e9, 1e9}); int Q; cin >> Q; for(int i = 1; i <= Q; i++){ int s, t, T; cin >> s >> t >> T; int j = upper_bound(b.begin()+1, b.end(), make_pair(t, 0)) - b.begin() - 1; ll ans = INF; for(int tt = 0; tt <= 1; tt++){ int jt = j + tt; if(jt > n || jt < 1) continue; ll res1 = abs(s - b[1].first) + f[jt][jt+1] + (ll)(pfcnt[n]+1) * abs(t - b[jt].first); ll res2 = abs(s - b[n].first) + g[jt][jt-1] + (ll)(pfcnt[n]+1) * abs(t - b[jt].first); ans = min({ans, res1, res2}); } if(ans <= T){ cout << "Yes"; }else{ cout << "No"; } cout << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }