#ifdef LOCAL

#else
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#endif

#include <bits/stdc++.h>

#include "candies.h"

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(24);
const ll inf = 1.5e9;

const int bsz = 450;
int n;
vector<ll> c;
int q;
vector<int> ql, qr;
vector<ll> qv;
vector<int> rs;
vector<ll> a;
vector<vector<ll>> ops;
int blcks;

vector<pair<ll, ll>> get_bbr(vector<ll> &ops, vector<pair<ll, ll>> &bbr) {
    vector<pair<ll, ll>> stck;
    stck.push_back(make_pair(0, inf));
    stck.reserve((int)ops.size());
    for (auto v : ops) {
        ll x = abs(v);
        if (v == 0) {
            continue;
        }
        if (v >= 0) {
            while (x > 0) {
                auto f = stck.back();
                stck.pop_back();
                if (f.second > x) {
                    f.second -= x;
                    f.first += x;
                    x = 0;
                    stck.push_back(f);
                    break;
                } else if (stck.empty()) {
                    f.first += f.second;
                    f.second = 0;
                    x = 0;
                    stck.push_back(f);
                    break;
                } else {
                    x -= f.second;
                    stck.back().first += f.first + f.second;
                }
            }
        } else {
            ll sm = 0;
            while (x > 0) {
                auto f = stck.back();
                stck.pop_back();
                if (f.first > x) {
                    f.first -= x;
                    stck.push_back(f);
                    sm += x;
                    x = 0;
                    break;
                } else if (stck.empty()) {
                    f.second += f.first;
                    f.first = 0;
                    x = 0;
                    stck.push_back(f);
                    break;
                } else {
                    x -= f.first;
                    sm += f.first + f.second;
                }
            }
            if (sm > 0) {
                stck.push_back(make_pair(0, sm));
            }
        }
    }
    bbr.clear();
    bbr.reserve((int)stck.size() * 2 + 1);
    ll sm = 0;
    ll pos = 0;
    bbr.push_back(make_pair(pos, sm));
    while (!stck.empty()) {
        auto f = stck.back();
        stck.pop_back();
        pos += f.first;
        sm += f.first;
        if (bbr.back().first != pos) {
            bbr.push_back(make_pair(pos, sm));
        }
        pos += f.second;
        if (bbr.back().first != pos) {
            bbr.push_back(make_pair(pos, sm));
        }
    }
    return bbr;
}

ll get_val(vector<pair<ll, ll>> &bbr, ll ps) {
    int j = upper_bound(all(bbr), make_pair(ps, inf * 5)) - bbr.begin();
    auto [ps0, sm0] = bbr[j - 1];
    auto [ps1, sm1] = bbr[j];
    ll val = ((ps1 - ps) * sm0 + (ps - ps0) * sm1) / (ps1 - ps0);
    return val;
}

void apply_operations(int l, int r, vector<ll> &ops) {
    if (ops.empty()) {
        return;
    }
    int sz = (int)ops.size();
    vector<ll> rops(sz);
    for (int i = 0; i < sz; i += 1) {
        rops[i] = -ops[i];
    }
    vector<pair<ll, ll>> bbr, rbbr;
    get_bbr(ops, bbr);
    get_bbr(rops, rbbr);
    vector<ll> mxs, mns;
    ll sm = 0;
    ll mx = 0;
    ll mn = 0;
    mns.resize(sz);
    mxs.resize(sz);
    for (int i = 0; i < sz; i += 1) {
        sm += ops[i];
        if (mx < sm) {
            mx = sm;
        }
        if (mn > sm) {
            mn = sm;
        }
        mns[i] = -mn;
        mxs[i] = mx;
    }
    for (int i = l; i <= r; i += 1) {
        ll x = a[i];
        int mxi = sz;
        int mni = sz;
        if(mxs.back() > c[i] - x){
            mxi = upper_bound(all(mxs), c[i] - x) - mxs.begin();
        }
        if(mns.back() > x){
            mni = upper_bound(all(mns), x) - mns.begin();
        }
        if (mxi == sz && mni == sz) {
            a[i] += sm;
        } else if (mxi < mni) {
            a[i] = c[i] - get_val(rbbr, c[i]);
        } else {
            a[i] = get_val(bbr, c[i]);
        }
    }
}

void apply_operations(int bi) {
    int l = bi * bsz;
    int r = min(n - 1, l + bsz - 1);
    apply_operations(l, r, ops[bi]);
    ops[bi].clear();
}

void solve() {
    rs.resize(n);
    blcks = (n + bsz - 1) / bsz;
    ops.assign(blcks, vector<ll>());
    a.assign(n, 0);
    for (int i = 0; i < q; i += 1) {
        int l = ql[i];
        int r = qr[i];
        ll v = qv[i];
        if (l / bsz == r / bsz) {
            apply_operations(l / bsz);
            for (int j = l; j <= r; j += 1) {
                a[j] = max(0ll, min(c[j], a[j] + v));
            }
            continue;
        }
        int lbi = l / bsz;
        int rbi = r / bsz;
        apply_operations(lbi);
        for (int j = l; j < (lbi + 1) * bsz; j += 1) {
            a[j] = max(0ll, min(c[j], a[j] + v));
        }
        apply_operations(rbi);
        for (int j = r; j >= rbi * bsz; j -= 1) {
            a[j] = max(0ll, min(c[j], a[j] + v));
        }
        for (int j = lbi + 1; j < rbi; j += 1) {
            ops[j].push_back(v);
        }
    }
    for (int i = 0; i < blcks; i += 1) {
        apply_operations(i);
    }
    for (int i = 0; i < n; i += 1) {
        rs[i] = a[i];
    }
}

void solve_l0_rn() {
    rs.resize(n);
    vector<pair<ll, ll>> bbr;
    get_bbr(qv, bbr);
    for (int i = 0; i < n; i += 1) {
        rs[i] = get_val(bbr, c[i]);
    }
}

vector<int> distribute_candies(vector<int> _c, vector<int> _l, vector<int> _r, vector<int> _v) {
    n = _c.size();
    q = _l.size();
    c.resize(n);
    for (int i = 0; i < n; i += 1) {
        c[i] = _c[i];
    }
    ql.resize(q);
    qr.resize(q);
    qv.resize(q);
    for (int i = 0; i < q; i += 1) {
        ql[i] = _l[i];
        qr[i] = _r[i];
        qv[i] = _v[i];
    }
    solve();
    return rs;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:8:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<long long int, std::allocator<long long int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~