#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Node{
map<int, int> mp;
int sum;
int lazy;
Node (){
sum=0;
lazy=1e18;
}
void merge(const Node &tl, const Node &tr){
sum=tl.sum+tr.sum;
lazy=1e18;
}
};
struct SegmentTree{
vector<Node> t;
void init(int n){
t.assign(4*n, Node());
}
void build(int k, int l, int r, int a[]){
if (l==r){
t[k].mp[a[l]]=1;
t[k].sum=a[l];
return;
}
int mid=(l+r)>>1;
build(k<<1, l, mid, a);
build(k<<1|1, mid+1, r, a);
t[k].merge(t[k<<1], t[k<<1|1]);
t[k].mp=t[k<<1].mp;
for (auto &i:t[k<<1|1].mp) t[k].mp[i.first]+=i.second;
}
void update_pos(int k, int l, int r, int pos, int val, int &old_val){
if (l==r){
old_val=t[k].mp.begin()->first;
t[k].mp.clear();
t[k].mp[val]=1;
t[k].sum=val;
t[k].lazy=1e18;
return;
}
push(k);
int mid=(l+r)>>1;
if (pos<=mid) update_pos(k<<1, l, mid, pos, val, old_val);
else update_pos(k<<1|1, mid+1, r, pos, val, old_val);
t[k].merge(t[k<<1], t[k<<1|1]);
++t[k].mp[val];
if (!--t[k].mp[old_val]) t[k].mp.erase(old_val);
}
void apply(int k, int val){
if (val<t[k].lazy){
t[k].lazy=val;
while (1){
auto it=prev(t[k].mp.end());
if (it->first<=val) break;
t[k].sum-=it->first*it->second;
int cnt=it->second;
t[k].mp.erase(it);
t[k].mp[val]+=cnt;
t[k].sum+=val*cnt;
}
}
}
void apply2(int k, int val, vector<pair<int, int>> &vv){
if (val<t[k].lazy){
t[k].lazy=val;
while (1){
auto it=prev(t[k].mp.end());
if (it->first<=val) break;
vv.push_back(*it);
t[k].sum-=it->first*it->second;
int cnt=it->second;
t[k].mp.erase(it);
t[k].mp[val]+=cnt;
t[k].sum+=val*cnt;
}
}
}
void apply3(int k, int val, vector<pair<int, int>> &vv){
for (auto &i:vv){
if (!(t[k].mp[i.first]-=i.second)) t[k].mp.erase(i.first);
t[k].mp[val]+=i.second;
}
}
void push(int k){
if (t[k].lazy!=1e18){
apply(k<<1, t[k].lazy);
apply(k<<1|1, t[k].lazy);
t[k].lazy=1e18;
}
}
void getmax(int k, int l, int r, int L, int R, pair<int, int> &m1, pair<int, int> &m2){
if (r<L || R<l) return ;
if (L<=l && r<=R){
auto it=prev(t[k].mp.end());
if (it->first>m1.first) m2=m1, m1=*it;
else if (it->first==m1.first) m1.second+=it->second;
else if (it->first>m2.first) m2=*it;
else if (it->first==m2.first) m2.second+=it->second;
if (it!=t[k].mp.begin()){
--it;
if (it->first>m2.first) m2=*it;
else if (it->first==m2.first) m2.second+=it->second;
}
return;
}
push(k);
int mid=(l+r)>>1;
getmax(k<<1, l, mid, L, R, m1, m2);
getmax(k<<1|1, mid+1, r, L, R, m1, m2);
}
int find_kth(int k, int l, int r, int L, int R, int val, int &cnt){
if (r<L || R<l || t[k].mp.rbegin()->first<val) return -1;
if (L<=l && r<=R && cnt>t[k].mp.rbegin()->second){
cnt-=t[k].mp.rbegin()->second;
return -1;
}
if (l==r) return l;
push(k);
int mid=(l+r)>>1;
int ans=find_kth(k<<1, l, mid, L, R, val, cnt);
if (ans!=-1) return ans;
return find_kth(k<<1|1, mid+1, r, L, R, val, cnt);
}
vector<pair<int, int>> update(int k, int l, int r, int L, int R, int val){
if (r<L || R<l) return {};
if (L<=l && r<=R){
vector<pair<int, int>> vv;
apply2(k, val, vv);
return vv;
}
push(k);
int mid=(l+r)>>1;
auto vl=update(k<<1, l, mid, L, R, val);
auto vr=update(k<<1|1, mid+1, r, L, R, val);
t[k].merge(t[k<<1], t[k<<1|1]);
vl.insert(vl.end(), vr.begin(), vr.end());
apply3(k, val, vl);
return vl;
}
int getsum(int k, int l, int r, int L, int R){
if (r<L || R<l) return 0;
if (L<=l && r<=R) return t[k].sum;
push(k);
int mid=(l+r)>>1;
return getsum(k<<1, l, mid, L, R)+getsum(k<<1|1, mid+1, r, L, R);
}
} st;
const int N=3e5+10;
int n, q, a[N];
void initialise(int32_t _n, int32_t _q, int32_t h[]){
n=_n; q=_q;
for (int i=1; i<=n; ++i) a[i]=h[i];
st.init(n);
st.build(1, 1, n, a);
}
void cut(int32_t l, int32_t r, int32_t k){
while (1){
pair<int, int> m1={0, 0}, m2={0, 0};
st.getmax(1, 1, n, l, r, m1, m2);
if (m1.first==0) break;
int d1=m1.second*(m1.first-m2.first);
if (k<=d1){
int pp=k/m1.second, qq=k%m1.second;
if (qq){
int id=st.find_kth(1, 1, n, l, r, m1.first, qq);
st.update(1, 1, n, l, id, m1.first-pp-1);
st.update(1, 1, n, id+1, r, m1.first-pp);
}else{
st.update(1, 1, n, l, r, m1.first-pp);
}
break;
}
k-=d1;
st.update(1, 1, n, l, r, m2.first);
}
}
void magic(int32_t i, int32_t x){
int val=-1;
st.update_pos(1, 1, n, i, x, val);
}
int inspect(int32_t l, int32_t r){
return st.getsum(1, 1, n, l, r);
}
