#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";
const int MAXLOG = 18;
const ll INF = 1'000'000'000'000'000;
vector<ll> a; //jaka odleglosc
vector<ll> b; //jaki koszt zakupu paliwa
vector<pair<ll, ll>> f_drzewo; //drzewo funkcji liniowych
vector<ll> odl_drzewo; //maksymalne drzewo po odl
vector<pair<ll, ll>> b_drzewo; //minimalne po koszcie paliwala
vector<ll> pref; //sumy prefiksowe do obliczania odleglosci
vector<ll> dpl; //tutaj tylko odl bo jp nie robimy
vector<pair<ll, int>> dpr; //jaka odleglosc do kolejnego tanszego na lewo i jaki to bedzie wierzcholek do jp
vector<vector<pair<ll, int>>> jp; //dokad doskaczymy i z jakim kosztem i z jaka odl
ll maks(int l, int r) {
ll wnk = max(odl_drzewo[l], odl_drzewo[r]);
while (r > (l + 1)) {
if (l%2 == 0) {
wnk = max(wnk, odl_drzewo[l + 1]);
}
if (r%2 == 1) {
wnk = max(wnk, odl_drzewo[r - 1]);
}
l /= 2;
r /= 2;
}
return wnk;
}
void zmien(int ind, pair<ll, ll> zmiana) {
f_drzewo[ind] = zmiana;
ind /= 2;
while (ind) {
f_drzewo[ind] = {f_drzewo[ind * 2].st + f_drzewo[(ind * 2) + 1].st, f_drzewo[ind * 2].nd + f_drzewo[(ind * 2) + 1].nd};
ind /= 2;
}
}
int minn(int l, int r) {
pair<ll, ll> wnk = min(b_drzewo[l], b_drzewo[r]);
while (r > (l + 1)) {
if (l%2 == 0) {
wnk = min(wnk, b_drzewo[l + 1]);
}
if (r%2 == 1) {
wnk = min(wnk, b_drzewo[r - 1]);
}
l /= 2;
r /= 2;
}
return wnk.nd;
}
pair<ll, ll> zlozenie(int l, int r) {
pair<ll, ll> wnk = {0, 0};
if (r < l) return wnk;
if (r == l) return f_drzewo[r];
wnk = {f_drzewo[r].st + f_drzewo[l].st, f_drzewo[r].nd + f_drzewo[l].nd};
while (r > (l + 1)) {
if (l%2 == 0) {
wnk.st += f_drzewo[l + 1].st;
wnk.nd += f_drzewo[l + 1].nd;
}
if (r%2 == 1) {
wnk.st += f_drzewo[r - 1].st;
wnk.nd += f_drzewo[r - 1].nd;
}
r /= 2;
l /= 2;
}
return wnk;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n>> q;
a.resize(n);
b.resize(n);
f(i, 0, n) cin >> a[i];
f(i, 0, n) cin >> b[i];
pref.resize(n + 1);
pref[0] = 0;
f(i, 1, n + 1) pref[i] = pref[i - 1] + a[i - 1];
dpl.resize(n);
stack<int> stos; //stos monotoniczny gdzie trzymam tylko ind
f(i, 0, n) {
while (sz(stos) && b[stos.top()] > b[i]) stos.pop();
if (sz(stos)) {
dpl[i] = pref[i] - pref[stos.top()];
} else {
dpl[i] = INF;
}
stos.push(i);
}
dpr.resize(n); //resizuje bo bede robic teraz stos monotoniczny i zapisywac wyniki
stos = {};
for (int i = n - 1; i >= 0; i--) {
while (sz(stos) && b[stos.top()] >= b[i]) stos.pop();
if (sz(stos)) {
dpr[i] = {pref[stos.top()] - pref[i], stos.top()};
} else {
dpr[i] = {INF, -1};
}
stos.push(i);
}
int stala = 1;
while (stala < n) stala *= 2;
odl_drzewo.resize((stala + 1) * 2);
f(i, 0, n) odl_drzewo[i + stala] = a[i];
f(i, n, stala) odl_drzewo[i + stala] = -INF;
for (int j = stala - 1; j > 0; j--) {
odl_drzewo[j] = max(odl_drzewo[j * 2], odl_drzewo[(2 * j) + 1]);
}
b_drzewo.resize((stala + 1) * 2);
f(i, 0, n) b_drzewo[i + stala] = {b[i], i};
f(i, n, stala) b_drzewo[i + stala] = {INF, INF};
for (int j = stala - 1; j > 0; j--) {
b_drzewo[j] = min(b_drzewo[j * 2], b_drzewo[(j * 2) + 1]);
}
jp.resize(MAXLOG, vector<pair<ll, int>>(n));
f(i, 0, n) {
if (dpr[i].st == INF) {
jp[0][i] = {0, i};
} else {
jp[0][i] = {b[i] * dpr[i].st, dpr[i].nd};
}
}
f(j, 1, MAXLOG) {
f(i, 0, n) {
jp[j][i] = {jp[j - 1][i].st + jp[j - 1][jp[j - 1][i].nd].st, jp[j - 1][jp[j - 1][i].nd].nd};
}
}
//na poc kazda funkcja ma y = x + 0
f_drzewo.resize((stala + 1) * 2);
f(i, 0, n) {
f_drzewo[i + stala] = {b[i], 0};
}
f(i, n, stala) {
f_drzewo[i + stala] = {0, 0};
}
for (int j = stala - 1; j > 0; j--) {
f_drzewo[j] = {f_drzewo[j * 2].st + f_drzewo[(j * 2) + 1].st, f_drzewo[j * 2].nd + f_drzewo[(j * 2) + 1].nd};
}
vector<pair<ll, pair<int, pair<int, pair<ll, ll>>>>> zamiatanie; //{jaki czas, {jaki rodzaj, {jaki ind, na co}}}
f(i, 0, n) {
zamiatanie.pb({min(dpl[i], dpr[i].st), {0, {i, {0, min(dpl[i], dpr[i].st) * b[i]}}}});
zamiatanie.pb({max(dpl[i], dpr[i].st), {0, {i, {-b[i], (dpl[i] + dpr[i].st) * b[i]}}}});
zamiatanie.pb({dpl[i] + dpr[i].st, {0, {i, {0, 0}}}});
}
vector<pair<pair<int, int>, ll>> pytania(q);
vector<ll> odp(q);
int ile_zrobione = 0;
f(i, 0, q) {
int l, r;
ll u;
cin >> l >> r >> u;
l--;
r--;
pytania[i] = {{l, r}, u};
if (maks(l + stala, r + stala - 1) > u) {
ile_zrobione++;
odp[i] = -1;
} else {
zamiatanie.pb({u, {1, {i, {-1, -1}}}});
}
}
sort(all(zamiatanie));
reverse(all(zamiatanie));
while (ile_zrobione < q) {
if (zamiatanie.empty()) {
cout << "blad";
return 0;
}
pair<ll, pair<int, pair<int, pair<ll, ll>>>> p1 = zamiatanie.back();
zamiatanie.pop_back();
int rodzaj = p1.nd.st;
int ind = p1.nd.nd.st;
if (rodzaj == 0) {
zmien(ind + stala, p1.nd.nd.nd);
continue;
}
ll aktl_u = pytania[ind].nd;
int l, r, mid; //by znalezc gdzie sie konczy nasz przedzial
int koniec = pytania[ind].st.nd;
r = pytania[ind].st.nd - 1;
l = pytania[ind].st.st;
while (r > l) {
mid = (l + r)/2;
if ((pref[koniec] - pref[mid]) <= aktl_u) {
r = mid;
} else {
l = mid + 1;
}
}
int suf_min = minn(r + stala, koniec - 1 + stala);
//cout << "o suf min pytam sie na przedziale " << r << " ... " << koniec - 1 << "\n";
//cout << "ind min suf to " << suf_min << "\n";
int poc = pytania[ind].st.st;
int skacze = poc;
ll ile_doda_skaczac = 0;
for (int j = MAXLOG - 1; j >= 0; j--) {
int p2 = jp[j][skacze].nd;
if ((pref[p2] - pref[poc]) <= aktl_u && p2 < koniec) {
ile_doda_skaczac += jp[j][skacze].st;
skacze = p2;
}
}
//cout << "skad start to " << skacze << "\n";
pair<ll, ll> nowa_funkcja = zlozenie(skacze + stala + 1, suf_min - 1 + stala);
//cout << "ile doda poc " << ile_doda_skaczac << "\n";
ll ile_doda_punkt = 0;
if (skacze < suf_min) {
ile_doda_punkt = min(min(pref[koniec] - pref[skacze], pref[suf_min] - pref[skacze]), min(aktl_u, dpr[skacze].st)) * b[skacze];
}
ll ile_doda_srodek = aktl_u * nowa_funkcja.st + nowa_funkcja.nd;
//cout << "suf min to " << suf_min << "\n";
//cout << "ile doda srodek " << ile_doda_srodek << " ile doda start " << ile_doda_skaczac << "\n";
ll ile_doda_kon = ((pref[koniec] - pref[suf_min]) * b[suf_min]);
if (dpl[suf_min] <= (pref[suf_min] - pref[poc])) {
ile_doda_kon -= (b[suf_min] * max((ll)0, (aktl_u - dpl[suf_min])));
}
//cout << "ile doda start " << ile_doda_skaczac << " ile doda srodek " << ile_doda_srodek << " ile doda kon " << ile_doda_kon << " ile doda punkt " << ile_doda_punkt << "\n";
odp[ind] = ile_doda_skaczac + ile_doda_srodek + ile_doda_kon + ile_doda_punkt;
ile_zrobione++;
}
for (ll ele: odp) {
cout << ele << "\n";
}
return 0;
}
