#include using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,tuple&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} templateistream &operator>>(istream &is,array&a){for(auto&i:a)is>>i;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template inline int fkey(vector&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #define SWITCH(a,b) (a) #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define SWITCH(a,b) (b) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i #include template constexpr std::enable_if_t::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template constexpr std::enable_if_t::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template constexpr std::enable_if_t,T>floor_pow2(T n){return n==0?0:T(1)< constexpr std::enable_if_t,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} template struct DynamicConvexHullTrick{ static_assert(std::is_integral_v); private: static constexpr T inf=std::numeric_limits::max(); struct line{ T a,b; int idx; line():a(0),b(inf),idx(-1){} line(T a_,T b_,int idx_):a(a_),b(b_),idx(idx_){} inline T operator()(T x)const{ return a*x+b; } bool operator<(const line&rhs)const{ if(a==rhs.a){ if(b==rhs.b)return idxrhs; if(std::min(a.idx,c.idx)>b.idx)return true; if(a.idx>b.idx&&a.a==b.a&&a.b==b.b)return true; if(c.idx>b.idx&&b.a==c.a&&b.b==c.b)return true; return false; } struct AVL{ struct avl_node{ avl_node *left,*right,*par; int8_t height; line lc,rc; line lm; bool lazy; avl_node():left(nullptr),right(nullptr),par(nullptr),height(0),lazy(false){} avl_node(T a,T b,int idx_):left(nullptr),right(nullptr),par(nullptr),height(0),lc(a,b,idx_),rc(a,b,idx_),lm(a,b,idx_),lazy(false){} inline int8_t diff()const{ return (left?left->height:0)-(right?right->height:0); } inline void light_update(){ lm=left->lm; height=std::max(left->height,right->height)+1; } inline void heavy_update(){ if(!lazy)return; left->heavy_update(); right->heavy_update(); avl_node *lnd=left,*rnd=right; T midx=rnd->lm.a; while(lnd->left||rnd->left){ if(lnd->left&&rnd->left){ if(!convex(lnd->lc,lnd->rc,rnd->lc)){ lnd=lnd->left; } else if(!convex(lnd->rc,rnd->lc,rnd->rc)){ rnd=rnd->right; } else{ if((T2(lnd->rc.b-lnd->lc.b)*T2(midx-lnd->lc.a)+T2(lnd->lc.b)*T2(lnd->rc.a-lnd->lc.a))*T2(rnd->rc.a-rnd->lc.a)<(T2(rnd->rc.b-rnd->lc.b)*T2(midx-rnd->lc.a)+T2(rnd->lc.b)*T2(rnd->rc.a-rnd->lc.a))*T2(lnd->rc.a-lnd->lc.a)){ lnd=lnd->right; } else{ rnd=rnd->left; } } } else if(lnd->left){ if(convex(lnd->lc,lnd->rc,rnd->lc))lnd=lnd->right; else lnd=lnd->left; } else{ if(convex(lnd->rc,rnd->lc,rnd->rc))rnd=rnd->left; else rnd=rnd->right; } } lc=lnd->lc,rc=rnd->rc; lazy=false; } }; static avl_node* rotl(avl_node*nd){ avl_node *ch=nd->right; if(nd->par){ if(nd->par->left==nd)nd->par->left=ch; else nd->par->right=ch; } ch->par=nd->par; nd->right=ch->left; nd->right->par=nd; ch->left=nd; nd->par=ch; return ch; } static avl_node* rotr(avl_node*nd){ avl_node *ch=nd->left; if(nd->par){ if(nd->par->left==nd)nd->par->left=ch; else nd->par->right=ch; } ch->par=nd->par; nd->left=ch->right; nd->left->par=nd; ch->right=nd; nd->par=ch; return ch; } static avl_node* balance(avl_node*nd){ if(nd->diff()==2){ if(nd->left->diff()==-1){ nd->left=rotl(nd->left); nd=rotr(nd); nd->left->light_update(); nd->right->light_update(); nd->light_update(); nd->left->lazy=nd->right->lazy=nd->lazy=true; } else{ nd=rotr(nd); nd->right->light_update(); nd->light_update(); nd->right->lazy=nd->lazy=true; } } else if(nd->diff()==-2){ if(nd->right->diff()==1){ nd->right=rotr(nd->right); nd=rotl(nd); nd->left->light_update(); nd->right->light_update(); nd->light_update(); nd->left->lazy=nd->right->lazy=nd->lazy=true; } else{ nd=rotl(nd); nd->left->light_update(); nd->light_update(); nd->left->lazy=nd->lazy=true; } } else{ nd->light_update(); nd->lazy=true; } return nd; } static void insert(avl_node*&root,T a,T b,int idx){ if(!root){ root=new avl_node(a,b,idx); return; } avl_node *nd=root; line ins(a,b,idx); while(nd->left){ if(insright->lm)nd=nd->left; else nd=nd->right; } avl_node *nch=new avl_node(a,b,idx); avl_node *np=new avl_node(); if(nd->par){ if(nd->par->left==nd)nd->par->left=np; else nd->par->right=np; np->par=nd->par; } nch->par=np; nd->par=np; if(inslm){ np->left=nch; np->right=nd; } else{ np->left=nd; np->right=nch; } while(true){ np=balance(np); if(np->par)np=np->par; else break; } root=np; } static bool erase(avl_node*&root,T a,T b,int idx=-1){ if(!root)return false; avl_node *nd=root; line era(a,b,idx); while(nd->left){ if(eraright->lm)nd=nd->left; else nd=nd->right; } if(!(era==nd->lm))return false; avl_node *p=nd->par; if(!p){ root=nullptr; delete nd; } else if(p->par){ avl_node *nnd; if(p->left==nd)nnd=p->right; else nnd=p->left; if(p->par->left==p)p->par->left=nnd; else p->par->right=nnd; nnd->par=p->par; delete p; delete nd; nnd=nnd->par; while(true){ nnd=balance(nnd); if(nnd->par)nnd=nnd->par; else break; } root=nnd; } else{ if(p->left==nd)root=p->right; else root=p->left; root->par=nullptr; delete p; delete nd; } return true; } }; typename AVL::avl_node *root; public: DynamicConvexHullTrick():root(nullptr){} void add(T a,T b,int idx=-1){ AVL::insert(root,a,b,idx); } bool erase(T a,T b,int idx=-1){ return AVL::erase(root,a,b,idx); } line min(T x)const{ if(!root)return line(0,inf,-1); root->heavy_update(); typename AVL::avl_node *nd=root; while(nd->left){ T leval=nd->lc(x),reval=nd->rc(x); if(levalleft; else if(leval>reval)nd=nd->right; else if(nd->lc.idxrc.idx)nd=nd->left; else nd=nd->right; } return nd->lc; } }; template struct SegmentTree{ using S=typename M::S; private: int n,z; std::vectordat; public: SegmentTree():n(0),z(0),dat(){} explicit SegmentTree(int n):n(n),z(ceil_pow2(n)),dat(ceil_pow2(n)*2,M::e()){} explicit SegmentTree(const std::vector&a):n(a.size()),z(ceil_pow2((int)a.size())){ dat.resize(z*2,M::e()); for(int i=0;i=1;i--)dat[i]=M::op(dat[i*2],dat[i*2+1]); } SegmentTree(int n,S init):SegmentTree(std::vector(n,init)){} inline S get(int i)const{return dat[i+z];} void set(int i,S x){ assert(0<=i&&i>=1; while(i){ dat[i]=M::op(dat[i*2],dat[i*2+1]); i>>=1; } } S prod(int l,int r)const{ assert(0<=l&&l<=r&&r<=n); l+=z,r+=z; S left=M::e(),right=M::e(); while(l>=1,r>>=1; } return M::op(left,right); } inline S all_prod()const{return dat[1];} template int max_right(int l,const Func&f){ if(l==n)return n; l+=z; S now=M::e(); do{ while((~l)&1)l>>=1; S nxt=M::op(now,dat[l]); if(f(nxt))now=nxt,l++; else{ while(l int min_left(int r,const Func&f){ if(r==0)return 0; r+=z; S now=M::e(); do{ r--; while(r>1&&(r&1))r>>=1; S nxt=M::op(dat[r],now); if(f(nxt))now=nxt; else{ while(r::max()> struct MonoidMin{ using S=T; using F=std::nullptr_t; static inline S op(const S&x,const S&y){return x>n>>h>>t; vectora(n); cin>>a; vectorinit(n); rep(i,n)init[i]=(h+a[i]-1)/a[i]; SegmentTree>seg(init); DynamicConvexHullTrickcht; auto add_line=[&](int idx,ll aa,ll bb)->void { cht.add(-aa,-bb,idx); }; auto get_max_and_erase=[&](ll x)->int { auto l=cht.min(x); assert(cht.erase(l.a,l.b,l.idx)); return l.idx; }; rep(i,n){ add_line(i,a[i],0); } ll add=0; vectorc(n); while(t--){ ll cnt=seg.all_prod()-add; int idx=get_max_and_erase(add+cnt); c[idx]++; seg.set(idx,(h+a[idx]-1)/a[idx]+add+cnt); add_line(idx,a[idx],a[idx]*(-add-cnt)); add+=cnt; } rep(i,n)cout<