#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
int n, q;
vector<int>c, l, r, v;
namespace sub1{
vector<int>solve(){
vector<int>ans(n, 0);
for(int i = 0; i < q; i++){
for(int j = l[i]; j <= r[i]; j++){
if(v[i] > 0){
ans[j] = min(c[j], ans[j] + v[i]);
}
else{
ans[j] = max(0, ans[j] + v[i]);
}
}
}
return ans;
}
}
namespace sub2{
vector<int>solve(){
vector<int>ans(n, 0);
vector<ll>f(n + 1, 0);
for(int i = 0; i < q; i++){
f[l[i]] += v[i];
f[r[i] + 1] -= v[i];
}
ans[0] = min(ll(c[0]), f[0]);
for(int i = 1; i < n; i++){
ans[i] = min(ll(c[i]), f[i] += f[i - 1]);
}
return ans;
}
}
const int lim = 2e5 + 5;
namespace sub3{
pair<int, int>st[lim << 2];
int lazy_1[lim << 2], lazy_2[lim << 2];
pair<int, int>merge(pair<int, int>a, pair<int, int>b){
return make_pair(min(a.first, b.first), max(a.second, b.second));
}
void propagate(int id, int x){
st[id].first += x;
st[id].second += x;
lazy_1[id] += x;
}
void push_down(int id){
if(lazy_2[id] != -1){
lazy_2[id << 1] = lazy_2[id << 1 | 1] = st[id << 1].first = st[id << 1].second = st[id << 1 | 1].first = st[id << 1 | 1].second = lazy_2[id];
lazy_1[id << 1] = lazy_1[id << 1 | 1] = 0;
lazy_2[id] = -1;
}
propagate(id << 1, lazy_1[id]);
propagate(id << 1 | 1, lazy_1[id]);
lazy_1[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
void refine(int id, int l, int r){
if(st[id].first > -1 && st[id].second <= c[0]){
return;
}
if(st[id].first >= c[0]){
st[id].first = st[id].second = lazy_2[id] = c[lazy_1[id] = 0];
return;
}
if(st[id].second < 1){
st[id].first = st[id].second = lazy_1[id] = lazy_2[id] = 0;
return;
}
int m = (l + r) >> 1;
push_down(id);
refine(id << 1, l, m);
refine(id << 1 | 1, m + 1, r);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
vector<int>ans;
void dfs(int id, int l, int r){
if(l == r){
ans.push_back(st[id].first);
return;
}
int m = (l + r) >> 1;
push_down(id);
dfs(id << 1, l, m);
dfs(id << 1 | 1, m + 1, r);
}
vector<int>solve(){
memset(lazy_1, 0, sizeof(lazy_1));
memset(lazy_2, -1, sizeof(lazy_2));
fill(st, st + (lim << 2), make_pair(0, 0));
for(int i = 0; i < q; i++){
update(1, 0, n - 1, l[i], r[i], v[i]);
refine(1, 0, n - 1);
}
dfs(1, 0, n - 1);
return ans;
}
}
const ll INF = 1e18;
namespace sub4{
vector<int>solve(){
vector<ll>pf(q + 1);
pf[0] = 0;
for(int i = 1; i <= q; i++){
pf[i] = pf[i - 1] + v[i - 1];
}
vector<ll>rmin = pf, rmax = pf;
for(int i = q - 1; i > -1; i--){
rmin[i] = min(rmin[i + 1], pf[i]);
rmax[i] = max(rmax[i + 1], pf[i]);
}
vector<int>ans(n);
for(int i = 0; i < n; i++){
int low = 0, high = q, p = -1;
while(low <= high){
int mid = (low + high) >> 1;
if(rmax[mid] - rmin[mid] > c[i]){
low = (p = mid) + 1;
}
else{
high = mid - 1;
}
}
if(p == -1){
ans[i] = pf[q] - rmin[0];
}
else if(pf[p] < pf[q]){
ans[i] = c[i] - rmax[p] + pf[q];
}
else{
ans[i] = pf[q] - rmin[p];
}
}
return ans;
}
}
namespace sub5{
pair<ll, ll>st[lim << 2];
ll lazy[lim << 2];
pair<ll, ll>merge(pair<ll, ll>a, pair<ll, ll>b){
return make_pair(min(a.first, b.first), max(a.second, b.second));
}
void propagate(int id, ll x){
st[id].first += x;
st[id].second += x;
lazy[id] += x;
}
void push_down(int id){
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
ll get(int p){
int id = 1, l = 0, r = q;
while(l < r){
int m = (l + r) >> 1;
push_down(id);
id <<= 1;
if(m < p){
id |= 1;
l = m + 1;
}
else{
r = m;
}
}
return st[id].first;
}
pair<ll, ll>get(int id, int l, int r, int u, int v){
if(l > v || r < u){
return make_pair(INF, -INF);
}
if(u <= l && v >= r){
return st[id];
}
int m = (l + r) >> 1;
push_down(id);
return merge(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
int walk(const int C){
int id = 1, l = 0, r = q, ans = -1;
ll cur_min = INF, cur_max = -INF;
while(l < r){
int m = (l + r) >> 1;
push_down(id);
id <<= 1;
if(max(cur_max, st[id | 1].second) - min(cur_min, st[id | 1].first) > C){
id |= 1;
l = ans = m + 1;
}
else{
minimize(cur_min, st[id | 1].first);
maximize(cur_max, st[id | 1].second);
r = m;
}
}
if(max(cur_max, st[id].second) - min(cur_min, st[id].first) > C){
ans = l;
}
return ans;
}
vector<int>event[lim];
vector<int>solve(){
memset(lazy, 0, sizeof(lazy));
fill(st, st + (lim << 2), make_pair(0, 0));
for(int i = 0; i < q; i++){
event[l[i]].push_back(i);
event[r[i] + 1].push_back(-i - 1);
}
vector<int>ans(n);
for(int i = 0; i < n; i++){
for(int& j : event[i]){
if(j < 0){
update(1, 0, q, -j, q, -v[-j - 1]);
}
else{
update(1, 0, q, j + 1, q, v[j]);
}
}
int p = walk(c[i]);
if(p == -1){
ans[i] = get(q) - st[1].first;
}
else if(get(p) < get(q)){
ans[i] = c[i] - get(1, 0, q, p, q).second + get(q);
}
else{
ans[i] = get(q) - get(1, 0, q, p, q).first;
}
}
return ans;
}
}
vector<int>distribute_candies(vector<int>_c, vector<int>_l, vector<int>_r, vector<int>_v){
swap(c, _c);
swap(l, _l);
swap(r, _r);
swap(v, _v);
if(max(n = c.size(), q = l.size()) <= 2000){
return sub1::solve();
}
if(*min_element(v.begin(), v.end()) > 0){
return sub2::solve();
}
if(count(c.begin(), c.end(), c[0]) == n){
return sub3::solve();
}
if(*max_element(l.begin(), l.end()) == 0 && *min_element(r.begin(), r.end()) == n - 1){
return sub4::solve();
}
return sub5::solve();
}
