#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
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'000LL;
vector<ll> a; //jaka odleglosc
vector<ll> b; //jaki koszt zakupu paliwa
vector<pair<ll, ll>> f_drzewo; //drzewo funkcji liniowych (slope, intercept)
vector<ll> odl_drzewo; //maksymalne drzewo po odl
vector<pair<ll, int>> b_drzewo; //minimalne po koszcie paliwala (cost, idx)
vector<ll> pref; //sumy prefiksowe do obliczania odleglosci
vector<ll> dpl; //odleglosc do najbliższego tanszego na lewo (albo INF)
vector<pair<ll, int>> dpr; //odleglosc do najbliższego tanszego na prawo i jego indeks
vector<vector<pair<ll, int>>> jp; //jump pointers: (cost_sum, next_index)
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, int> 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;
if (!(cin >> n >> q)) return 0;
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;
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);
{
stack<int> 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.assign(2 * stala, -INF);
f(i, 0, n) odl_drzewo[i + stala] = a[i];
for (int j = stala - 1; j > 0; j--) {
odl_drzewo[j] = max(odl_drzewo[j * 2], odl_drzewo[(2 * j) + 1]);
}
b_drzewo.assign(2 * stala, {INF, INT_MAX});
f(i, 0, n) b_drzewo[i + stala] = {b[i], i};
for (int j = stala - 1; j > 0; j--) {
b_drzewo[j] = min(b_drzewo[j * 2], b_drzewo[(j * 2) + 1]);
}
jp.assign(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 };
}
}
// inicjalizacja f_drzewo (liście)
f_drzewo.assign(2 * stala, {0, 0});
f(i, 0, n) {
f_drzewo[i + stala] = {b[i], 0}; // zostawiam twoją pierwotną inicjalizację liści
}
for (int j = stala - 1; j > 0; j--) {
// POPRAWKA: sumujemy też .nd (wcześniej było 0)
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; //{u, {rodzaj, {ind, {slope, intercept}}}}
f(i, 0, n) {
// eventy (tak jak w Twoim kodzie)
ll mn = min(dpl[i], dpr[i].st);
ll mx = max(dpl[i], dpr[i].st);
zamiatanie.pb({mn, {0, {i, {0, mn * b[i]}}}});
zamiatanie.pb({mx, {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\n";
return 0;
}
auto ev = zamiatanie.back();
zamiatanie.pop_back();
int rodzaj = ev.nd.st;
int ind = ev.nd.nd.st;
if (rodzaj == 0) {
zmien(ind + stala, ev.nd.nd.nd);
continue;
}
ll aktl_u = pytania[ind].nd;
int l, r, mid;
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);
int poc = pytania[ind].st.st;
int skacze = poc;
ll ile_doda_skaczac = 0;
for (int j = MAXLOG - 1; j >= 0; j--) {
int to = jp[j][skacze].nd;
if ((pref[to] - pref[poc]) <= aktl_u && to < koniec) {
ile_doda_skaczac += jp[j][skacze].st;
skacze = to;
}
}
pair<ll, ll> nowa_funkcja = zlozenie(skacze + stala + 1, suf_min - 1 + stala);
ll ile_doda_punkt = 0;
if (skacze < suf_min) {
// POPRAWKA: ograniczamy do środka (suf_min), a nie do 'koniec'
ll limit = pref[suf_min] - pref[skacze];
ile_doda_punkt = min(limit, min(aktl_u, dpr[skacze].st)) * b[skacze];
}
ll ile_doda_srodek = aktl_u * nowa_funkcja.st + nowa_funkcja.nd;
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])));
}
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;
}
