#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = (1<<19); const ll E = 19; const ll INF = 2e9;
map<ll,ll> stn[2*Nm];
ll stm[2*Nm];
ll sts[2*Nm];
ll lz[2*Nm];
ll N;
void initialise(int _N, int _Q, int h0[]) {
N = _N;
for (ll i=0;i<N;i++) {
stn[i+Nm][h0[i]]=1;
lz[i+Nm]=INF;
sts[i+Nm]=h0[i];
stm[i+Nm]=h0[i];
}
for (ll i=N;i<Nm;i++) {
stn[i+Nm][0]=1;
lz[i+Nm]=INF;
sts[i+Nm]=0;
stm[i+Nm]=0;
}
for (ll p=(Nm-1);p>=1;p--) {
for (pii p0: stn[2*p]) {
stn[p][p0.first]+=p0.second;
}
for (pii p0: stn[2*p+1]) {
stn[p][p0.first]+=p0.second;
}
sts[p]=sts[2*p]+sts[2*p+1];
stm[p]=max(stm[2*p],stm[2*p+1]);
lz[p]=INF;
}
// for (ll p=1;p<(2*Nm);p++) {
// cout << "sts[p="<<p<<"]="<<sts[p]<<"\n";
// }
}
void lft(ll h0, ll hf, ll qt, ll p) {
//DO NOT PUSH DOWN
if (p==0) {
return;
}
sts[p]+=qt*(hf-h0);
stn[p][hf]+=qt;
stn[p][h0]-=qt;
if (stn[p][h0]==0) {
stn[p].erase(h0);
}
stm[p]=(*(--stn[p].end())).first;
lft(h0,hf,qt,p/2);
}
void pdn(ll p) {
if (p==0 || lz[p]==INF) {
return;
}
while (!stn[p].empty()) {
auto A0 = --stn[p].end();
pii pf = *A0;
if (pf.first<=lz[p]) {
break;
} else {
//cout << "push down pdn at p="<<p<<"\n";
//cout << "lz[p]="<<lz[p]<<", pf="<<pf.first<<","<<pf.second<<"\n";
sts[p]-=(pf.first-lz[p])*pf.second;
stm[p]=lz[p];
stn[p].erase(A0);
stn[p][lz[p]]+=pf.second;
}
}
if (p<Nm) {
lz[2*p]=min(lz[2*p],lz[p]);
lz[2*p+1]=min(lz[2*p+1],lz[p]);
}
lz[p]=INF;
}
inline ll v2(ll x) {
return __builtin_ctz(x);
}
void cut2(ll p, ll mval, ll k) {
//cout << "cut2: p,mval,k="<<p<<","<<mval<<","<<k<<"\n";
if (k==0) {
return;
}
for (ll e=E;e>=0;e--) {
pdn(p>>e);
}
if (stn[p][mval]==k) {
lft(mval,mval-1,k,p);
lz[p]=mval-1;
return;
}
assert(p<Nm);
if (stn[2*p].find(mval)==stn[2*p].end()) {
cut2(2*p+1,mval,k);
} else if (stn[2*p][mval]>=k) {
cut2(2*p,mval,k);
} else {
cut2(2*p+1,mval,k-stn[2*p][mval]);
//cout << "loopbk\n";
cut2(2*p,mval,stn[2*p][mval]);
}
}
void cut(int l, int r, int k) {
if (k==0) {
return;
}
l--; r--;
ll l0 = l; ll r0 = r;
ll mval = 0;
vector<pii> vc;
while (l0<=r0) {
ll vl = v2(l0); ll vr = v2(r0+1);
if (vl<vr) {
ll p0 = (l0>>vl)+(1<<(E-vl));
for (ll e=E;e>=0;e--) {
pdn(p0>>e);
}
if (stm[p0]>mval) {
vc.clear();
mval = stm[p0];
}
if (stm[p0]==mval) {
vc.push_back({l,p0});
}
l0+=(1<<vl);
} else {
ll p0 = (r0>>vr)+(1<<(E-vr));
for (ll e=E;e>=0;e--) {
pdn(p0>>e);
}
if (stm[p0]>mval) {
vc.clear();
mval = stm[p0];
}
if (stm[p0]==mval) {
vc.push_back({r,p0});
}
r0-=(1<<vr);
}
}
if (mval==0) {
return;
}
sort(vc.begin(),vc.end());
for (pii PQ: vc) {
if (k==0) {
return;
}
ll p0 = PQ.second;
if (stn[p0][mval]<=k) {
k -= stn[p0][mval];
lz[p0]=min(lz[p0],mval-1);
lft(mval,mval-1,stn[p0][mval],p0);
} else {
cut2(p0,mval,k);
k=0;
}
}
cut(l+1,r+1,k);
}
void magic(int i, int x) {
i--;
for (ll e=E;e>=0;e--) {
pdn((i>>e)+(1<<(E-e)));
}
ll ht0 = (*stn[i+Nm].begin()).first;
lft(ht0,x,1,i+Nm);
}
ll inspect(int l, int r) {
ll fval = 0;
l--; r--;
ll l0=l; ll r0=r;
while (l0<=r0) {
ll vl = v2(l0); ll vr = v2(r0+1);
if (vl<vr) {
ll p0 = (l0>>vl)+(1<<(E-vl));
for (ll e=E;e>=0;e--) {
pdn(p0>>e);
}
fval += sts[p0];
l0 += (1<<vl);
} else {
ll p0 = (r0>>vr)+(1<<(E-vr));
for (ll e=E;e>=0;e--) {
pdn(p0>>e);
}
fval += sts[p0];
r0 -= (1<<vr);
}
}
return fval;
}
