// coached by rainboy #include <algorithm> #include <iostream> using namespace std; const int N = 200000; const int Q = 200000; const int N_ = 1 << 18; long long aa[N + 1]; int cc[N + 1]; int ll[Q], rr[Q], zz[Q]; long long xx[Q]; long long bb[N << 1]; int ii[N << 1]; int pq[N], iq[N + 1], pq_cnt; long long aa_[N << 1], pp[N << 1]; int cc_[N << 1]; int qu[N]; long long qq[N]; int st[N_ << 1], n_; bool lt(int i, int j) { return cc[i] < cc[j]; } int p2(int p) { return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p + 1], iq[p])); } void pq_up(int i) { int j, p, q; for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_dn(int i) { int j, p, q; for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_add(int i) { pq[i] = ++pq_cnt, pq_up(i); } void pq_remove(int i) { int j = iq[pq_cnt--]; if (i != j) pq[j] = pq[i], pq_up(j), pq_dn(j); pq[i] = 0; } long long calc(long long a, int m) { int lower = -1, upper = m; while (upper - lower > 1) { int h = lower + upper >> 1; if (a <= aa_[h]) upper = h; else lower = h; } int h = upper; if (h == m) return -1; if (!h) return cc_[h] * a; return pp[h - 1] + cc_[h] * (a - aa_[h - 1]); } void pul(int i) { int l = i << 1, r = l ^ 1; st[i] = max(st[l], st[r]); } void build(int n) { for (n_ = 1; n_ < n; n_ <<= 1) ; for (int i = 0; i < n; i++) st[i + n_] = aa[i + 1] - aa[i]; for (int i = n_ - 1; i; i--) pul(i); } int query(int l, int r) { int a = 0; for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) { if (l & 1) a = max(a, st[l++]); if (!(r & 1)) a = max(a, st[r--]); } return a; } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> aa[i], aa[i] += aa[i - 1]; for (int i = 0; i < n; i++) cin >> cc[i]; int d; for (int z = 0; z < q; z++) cin >> ll[z] >> rr[z] >> d, ll[z]--, rr[z]--, zz[z] = z; for (int i = 0; i < n << 1; i++) bb[ii[i] = i] = aa[i >> 1] + (i & 1 ? d : 0); sort(ii, ii + (n << 1), [] (int i, int j) { return bb[i] < bb[j]; }); int m = 0; for (int h = 0; h < n << 1; ) { long long a = bb[ii[h]]; aa_[m] = a, cc_[m] = pq_cnt ? cc[iq[1]] : -1, m++; for ( ; h < n << 1 && bb[ii[h]] == a; h++) { int i = ii[h] >> 1; if (!pq[i]) pq_add(i); else pq_remove(i); } } pp[0] = cc_[0] * aa_[0]; for (int h = 1; h < m; h++) pp[h] = pp[h - 1] + cc_[h] * (aa_[h] - aa_[h - 1]); for (int z = 0; z < q; z++) { int l = aa[ll[z]], r = aa[rr[z]]; if (l + d <= r) xx[z] = calc(r, m) - calc(l + d - 1, m); } sort(zz, zz + q, [] (int z0, int z1) { return ll[z0] > ll[z1]; }); for (int cnt = 0, i = n - 1, y = 0; i >= 0; i--) { while (cnt && cc[i] <= cc[qu[cnt - 1]]) cnt--; qu[cnt] = i, qq[cnt] = cnt ? qq[cnt - 1] + cc[i] * (aa[qu[cnt - 1]] - aa[i]) : 0, cnt++; for (int z; y < q && ll[z = zz[y]] == i; y++) { int a = min(aa[i] + d - 1, aa[rr[z]]), lower = -1, upper = cnt - 1; while (upper - lower > 1) { int h = lower + upper >> 1; if (aa[qu[h]] < a) upper = h; else lower = h; } int h = upper, j = qu[h]; xx[z] += qq[cnt - 1] - qq[h] + cc[j] * (a - aa[j]); } } build(n); for (int z = 0; z < q; z++) cout << (query(ll[z], rr[z] - 1) <= d ? xx[z] : -1) << '\n'; return 0; }