#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e16;
static const int N = 200015;
// We replicate the same structures from the “correct code.”
// ========== Segment Tree for range-add, point-query ==========
struct seg {
// We store data in a 1D array tree[2*N].
// query(i): returns the sum from root to leaf i.
// update(l, r, val): adds val to [l..r].
ll tree[2*N];
// Returns the prefix-sum-like query at index i.
ll query(int i){
ll res = 0;
for(i += N; i > 0; i >>= 1){
res += tree[i];
}
return res;
}
// Add “x” to all elements in [l..r].
void update(int l, int r, ll x){
// 0-based => we store data from N..2N-1 in the leaves
for(l += N, r += N+1; l < r; l >>= 1, r >>= 1){
if(l & 1) tree[l++] += x;
if(r & 1) tree[--r] += x;
}
}
};
// ========== Segment Tree for range-max query ==========
struct segmax {
ll tree[2*N];
// Returns max in [l..r].
ll query(int l, int r){
ll res = -INF;
for(l += N, r += N+1; l < r; l >>= 1, r >>= 1){
if(l & 1) res = max(res, tree[l++]);
if(r & 1) res = max(res, tree[--r]);
}
return res;
}
// Update position i with value x = max(tree[i], x).
void update(int i, ll x){
for(i += N; i > 0; i >>= 1){
tree[i] = max(tree[i], x);
}
}
};
// ========== Segment Tree for range-min query (storing (value, index)) ==========
struct segmin {
pi tree[2*N]; // (value, index)
// Returns min in [l..r] by comparing .first
pi query(int l, int r){
pi res = mp(INF, INF);
for(l += N, r += N+1; l < r; l >>= 1, r >>= 1){
if(l & 1) {
if(tree[l].f < res.f) res = tree[l];
l++;
}
if(r & 1) {
--r;
if(tree[r].f < res.f) res = tree[r];
}
}
return res;
}
// Update position i with x if x is “smaller”
void update(int i, pi x){
for(i += N; i > 0; i >>= 1){
if(x.f < tree[i].f) tree[i] = x;
}
}
};
// Query struct (same as correct code)
struct query {
ll U, id, mul;
};
// Global arrays
ll n, Q;
ll X[N], B[N], Rpos[N]; // Rpos corresponds to R[i] in the correct code
ll ans[N];
// For queries
vector<query> queriesAt[N];
// For discretizing “U”
vector<ll> dis;
// Returns index in “dis” for upper_bound on i
int getidx(ll i){
return (int)(upper_bound(all(dis), i) - dis.begin());
}
// Our main data structures
seg mAdd, cAdd;
segmax finddie;
segmin getmin;
// ---------------------------- main ----------------------------
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> Q;
// Input for X[2..n+1]
for(int i = 2; i <= n+1; i++){
cin >> X[i];
}
// Input for B[1..n]
for(int i = 1; i <= n; i++){
cin >> B[i];
}
// Initialize
// Clears the segment trees
for(int i = 0; i < 2*N; i++){
mAdd.tree[i] = 0;
cAdd.tree[i] = 0;
finddie.tree[i] = -INF;
getmin.tree[i] = mp(INF, INF);
}
// Build segmax for the “gap check” finddie
// We do finddie.update(i-1, X[i]) for i=2..n+1
for(int i = 2; i <= n+1; i++){
finddie.update(i-1, X[i]);
}
// Build segmin for B[] so we can query min B in [s..t-1]
// i in [1..n]
for(int i = 1; i <= n; i++){
getmin.update(i, mp(B[i], i));
}
// Build prefix sums in X[]
for(int i = 2; i <= n+1; i++){
X[i] += X[i - 1];
}
// Process queries
for(int i = 1; i <= Q; i++){
int s, t, u;
cin >> s >> t >> u;
// If the max gap in [s..t-1] > u => ans[i] = -1
// Using segmax => finddie.query(s, t-1)
if(finddie.query(s, t-1) > u) {
ans[i] = -1;
}
else {
// We'll add to queriesAt[s], queriesAt[somethingElse], etc.
// queries[s].push_back({u, i, +1});
queriesAt[s].pb({(ll)u, (ll)i, +1LL});
// findpos = lower_bound(X+1, X+n+1, X[t] - u) - X;
int findpos = (int)(lower_bound(X + 1, X + (n + 1), X[t] - u) - X);
// Query segmin in [max(s, findpos) .. t-1] => get (BMin, indexMin)
int leftBound = max(s, findpos);
pi ret = getmin.query(leftBound, t - 1);
ll tmiddle = ret.s; // the index with min B
// queries[tmiddle].push_back({u, i, -1});
queriesAt[tmiddle].pb({(ll)u, (ll)i, -1LL});
// ans[i] += (X[t] - X[tmiddle]) * B[tmiddle]
ans[i] += (X[t] - X[tmiddle]) * B[tmiddle];
// Also push “u” into dis
dis.pb(u);
}
}
// Now push INF to dis and do unique
dis.pb(INF);
discretize(dis);
// We proceed with the stack-based logic
// stack<int> st; B[n+1] = -inf; st.push(n+1);
// The correct code sets B[n+1] = -INF as sentinel
B[n+1] = -INF;
stack<int> st;
st.push(n+1);
// We'll sweep from s=n down to 1
ll maxdis = 0;
for(int s = n; s >= 1; s--){
// Keep track of maximum gap so far (not essential to the final logic,
// but present in the code)
maxdis = max(maxdis, X[s+1] - X[s]);
// while(B[st.top()] >= B[s]) => pop
while(!st.empty() && B[st.top()] >= B[s]){
int i = st.top();
st.pop();
// Use R[i] => which is Rpos[i] in our code
// but we have NOT set Rpos[i] yet. We want the same approach as the original:
// Actually, the original sets R[s] AFTER popping bigger B[] from the stack.
// So for i, we do:
// d1 = get( X[i] - X[s] )
// d2 = get( X[R[i]] - X[s] )
// mAdd.update(d1+1, d2, -B[i])
// cAdd.update(d1+1, d2, (X[i]-X[s])*B[i])
// cAdd.update(d2+1, N-1, (X[R[i]]-X[i]) * -B[i])
ll d1 = getidx(X[i] - X[s]);
ll d2 = getidx(X[Rpos[i]] - X[s]);
// update in [d1+1..d2] => -B[i]
// note that “correct code” is 1-based for segment indexes, so we do the same
mAdd.update(d1 + 1, d2, -B[i]);
cAdd.update(d1 + 1, d2, (X[i] - X[s]) * B[i]);
cAdd.update(d2 + 1, (int)dis.size() - 1, (X[Rpos[i]] - X[i]) * (-B[i]));
}
// Now st.top() is the next boundary
int r = st.top();
Rpos[s] = r;
// Then we do the “add the min(X[r] - X[s])” logic
// D = get( X[r] - X[s] )
ll D = getidx(X[r] - X[s]);
// Then update:
// mAdd.update(1, D, B[s])
// cAdd.update(D+1, end, (X[r]-X[s])*B[s])
mAdd.update(1, D, B[s]);
cAdd.update(D+1, (int)dis.size() - 1, (X[r] - X[s]) * B[s]);
// push s
st.push(s);
// Now apply queries that start at s
for(auto &q : queriesAt[s]){
ll uVal = q.U, qid = q.id, mulSign = q.mul;
// get idx for uVal => disc
ll idxU = getidx(uVal);
// ans[qid] += mulSign * ( mAdd.query(idxU)*uVal + cAdd.query(idxU) )
ans[qid] += mulSign * ( mAdd.query(idxU)*uVal + cAdd.query(idxU) );
}
}
// Output final answers
for(int i = 1; i <= Q; i++){
cout << ans[i] << endl;
}
return 0;
}
