#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct line
{
ll a = 0,b = 0;
line operator+(const line& other)
{
return {a+other.a,b+other.b};
}
ll operator()(ll u)
{
return u*a+b;
}
bool operator<(const line& other) const
{
return a < other.a;
}
};
struct query
{
int l,r;
ll u;
int ind;
bool operator<(const query& other) const
{
return u < other.u;
}
};
const int tree_siz = 1024*512-1;
int drzewo_A[tree_siz];
int get_max_A(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return 0;
if(p1 >= s1 && p2 <= s2)
{
return drzewo_A[akt-1];
}
return max(get_max_A(akt*2,p1,(p1+p2)/2,s1,s2),get_max_A(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}
void updA(int v)
{
drzewo_A[v-1] = max(drzewo_A[v*2-1],drzewo_A[v*2]);
if(v != 1) updA(v/2);
}
void changeA(int ind, int x)
{
drzewo_A[tree_siz/2+ind] = x;
updA((tree_siz/2+ind+1)/2);
}
line ltree[tree_siz];
line get_f(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return {0,0};
if(p1 >= s1 && p2 <= s2) return ltree[akt-1];
return get_f(akt*2,p1,(p1+p2)/2,s1,s2) + get_f(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
}
void updl(int v)
{
ltree[v-1] = ltree[v*2-1] + ltree[v*2];
if(v != 1) updl(v/2);
}
void change_f(int ind, line f)
{
ltree[tree_siz/2+ind] = f;
updl((tree_siz/2+ind+1)/2);
}
ll A_pref[200'002];
ll cost[200'002];
int prev_[200'002];
int nxt[200'002];
ll L[200'002];
ll R[200'002];
ll query_ans[200'002];
bool was_intersect[200'002];
int query_T[200'002];
int query_S[200'002];
ll query_U[200'002];
int qu_l[200'002];
int qu_r[200'002];
vector<pair<int,pll>> events_pref[200'002];
vector<pair<int,pll>> events_suf[200'002];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int n,q;
cin >> n >> q;
A_pref[0] = 1e9;
rep2(i,1,n)
{
ll a;
cin >> a;
A_pref[i] = A_pref[i-1] + a;
changeA(i,a);
}
A_pref[n+1] = A_pref[n];
rep2(i,1,n) cin >> cost[i];
stack<int> st;
for(int i = n; i >= 0; i--)
{
while(!st.empty() && cost[st.top()] > cost[i])
{
st.pop();
}
if(siz(st) == 0)
{
nxt[i] = n+1;
}
else
{
nxt[i] = st.top();
}
st.push(i);
}
st = {};
rep2(i,1,n)
{
while(!st.empty() && cost[st.top()] >= cost[i])
{
st.pop();
}
if(siz(st) == 0)
{
prev_[i] = 0;
}
else
{
prev_[i] = st.top();
}
st.push(i);
}
rep2(i,1,n)
{
if(prev_[i] > 0) L[i] = A_pref[i-1] - A_pref[prev_[i]-1];
else L[i] = 1e18;
R[i] = A_pref[nxt[i]-1] - A_pref[i-1];
}
vector<pair<ll,pair<int,line>>> events;
rep2(i,1,n)
{
if(L[i] < R[i])
{
events.pb({0,{i,{cost[i],0}}});
events.pb({L[i],{i,{0,cost[i] * L[i]}}});
events.pb({R[i],{i,{-cost[i],cost[i] * (L[i] + R[i])}}});
events.pb({L[i] + R[i],{i,{0,0}}});
}
else if(L[i] > R[i])
{
events.pb({0,{i,{cost[i],0}}});
events.pb({R[i],{i,{0,cost[i] * R[i]}}});
events.pb({L[i],{i,{-cost[i],cost[i] * (L[i] + R[i])}}});
events.pb({L[i] + R[i],{i,{0,0}}});
}
else
{
events.pb({0,{i,{cost[i],0}}});
events.pb({R[i],{i,{-cost[i],cost[i] * (L[i] + R[i])}}});
events.pb({L[i] + R[i],{i,{0,0}}});
}
}
vector<query> qu;
rep(qq,q)
{
int s,t;
ll u;
cin >> s >> t >> u;
query_T[qq] = t-1;
query_S[qq] = s;
query_U[qq] = u;
t--;
if(get_max_A(1,0,tree_siz/2,s,t) > u)
{
query_ans[qq] = -1;
continue;
}
int l = s;
int r = t;
int u_pref = s;
while(l <= r)
{
int mid = (l+r)/2;
if(A_pref[mid-1] - A_pref[s-1] <= u)
{
u_pref = mid;
l = mid+1;
}
else
{
r = mid-1;
}
}
l = s;
r = t;
int u_suf = t;
while(l <= r)
{
int mid = (l+r)/2;
// cerr << mid << " " << A_pref[t] - A_pref[mid-1] << " bin\n";
if(A_pref[t] - A_pref[mid-1] <= u)
{
u_suf = mid;
r = mid-1;
}
else
{
l = mid+1;
}
}
// cerr << u_pref << " " << u_suf << " pref/suf\n";
// if(u_pref < u_suf)
// {
// if(u_pref + 1 != u_suf)
// {
// qu.pb({u_pref+1,u_suf-1,u,qq});
// }
// }
events_pref[s].pb({qq,{u_pref,u}});
events_suf[u_suf].pb({qq,{t,u}});
}
//pref calc:
vector<pll> stp;
for(int i = n; i >= 1; i--)
{
while(siz(stp) != 0 && cost[i] < cost[stp.back().ff])
{
stp.pop_back();
}
if(siz(stp) == 0)
{
stp.pb({i,0});
}
else
{
stp.pb({i,stp.back().ss + cost[i] * (A_pref[stp.back().ff-1] - A_pref[i-1])});
}
forall(it,events_pref[i])
{
int ind = it.ff;
ll u = it.ss.ss;
int l = 0;
int r = siz(stp)-1;
int ans = 0;
while(l <= r)
{
int mid = (l+r)/2;
if(A_pref[stp[mid].ff-1] - A_pref[i-1] <= u && stp[mid].ff <= query_T[ind])
{
ans = mid;
r = mid-1;
}
else
{
l = mid+1;
}
}
query_ans[ind] += stp.back().ss - stp[ans].ss;
// cerr << query_ans[ind] << " " << ans << " " << stp[ans].ff << " L_add\n";
qu_l[ind] = stp[ans].ff+1;
int v = stp[ans].ff;
if(nxt[v] <= query_T[ind] || A_pref[query_T[ind]] - A_pref[v-1] > it.ss.ss)
{
query_ans[ind] += cost[v] * min(it.ss.ss,A_pref[nxt[v]-1] - A_pref[v-1]);
}
else
{
qu_r[ind] = -1;
was_intersect[ind] = 1;
query_ans[ind] += cost[v] * min(it.ss.ss,A_pref[query_T[ind]] - A_pref[v-1]);
}
// cerr << query_ans[ind] << " L_add\n";
}
}
//suf calc
vector<int> stc;
for(int i = n; i >= 1; i--)
{
while(siz(stc) != 0 && nxt[i] >= nxt[stc.back()])
{
stc.pop_back();
}
stc.pb(i);
forall(it,events_suf[i])
{
if(was_intersect[it.ff]) continue;
int l = 0;
int r = siz(stc)-1;
int ans = 0;
while(l <= r)
{
int mid = (l+r)/2;
if(nxt[stc[mid]] > query_T[it.ff])
{
ans = mid;
l = mid+1;
}
else
{
r = mid-1;
}
}
int v = stc[ans];
qu_r[it.ff] = v-1;
ll l2 = 0;
if(prev_[v] >= query_S[it.ff]) l2 = A_pref[v-1] - A_pref[prev_[v]-1];
else l2 = 1e18;
ll r2 = 0;
if(nxt[v] <= query_T[it.ff]) r2 = A_pref[nxt[v]-1] - A_pref[v-1];
else r2 = A_pref[query_T[it.ff]] - A_pref[v-1];
// cout << i << " " << l << " " << r << " " << u << " " << ans << " " << max(min(u,r) - max(u-l,0LL),0LL)<< " ans\n";
query_ans[it.ff] += max(min(it.ss.ss,r2) - max(it.ss.ss-l2,0LL),0LL) * cost[v];
// cerr << query_ans[it.ff] << " R_add\n";
}
}
rep(qq,q)
{
if(qu_l[qq] <= qu_r[qq])
{
qu.pb({qu_l[qq],qu_r[qq],query_U[qq],qq});
// cerr << qu_l[qq] << " " << qu_r[qq] << " qq\n";
}
}
sort(all(qu));
sort(all(events));
int cur_e = 0;
forall(it,qu)
{
while(cur_e < siz(events) && events[cur_e].ff <= it.u)
{
change_f(events[cur_e].ss.ff,events[cur_e].ss.ss);
cur_e++;
}
query_ans[it.ind] += get_f(1,0,tree_siz/2,it.l,it.r)(it.u);
}
rep(i,q) cout << query_ans[i] << "\n";
}
