#pragma once
namespacew_ary_tree_impl{usingu64=uint64_t;staticconstexprunsignedintlgW=6;staticconstexprunsignedintW=1u<<lgW;staticconstexprintinf=1<<30;inlineintctz(u64n){returnn?__builtin_ctzll(n):-1;}inlineintclz(u64n){returnn?63-__builtin_clzll(n):-1;}template<intLOG,classD=void>structw_ary_tree_node{u64map;intmn,mx;staticconstexprintshift=(LOG-1)*lgW;array<w_ary_tree_node<LOG-1>,W>chd;inlineintmask(u64key)const{returnkey&((1<<shift)-1);}w_ary_tree_node():map(0),mn(inf),mx(-1){}voidinsert(intkey){mn=std::min(mn,key),mx=std::max(mx,key);intpos=key>>shift;map|=1ULL<<pos;chd[pos].insert(mask(key));}voiderase(intkey){intpos=key>>shift;chd[pos].erase(mask(key));if(chd[pos].map==0)map&=~(1ULL<<pos);if(mn==key){if(mx==key){mn=inf,mx=-1;}else{intp=ctz(map);mn=(p<<shift)+chd[p].min();}}elseif(mx==key){intp=clz(map);mx=(p<<shift)+chd[p].max();}}boolcontain(intkey)const{intpos=key>>shift;returnchd[pos].contain(mask(key));}inlineintmin()const{returnmn==inf?-1:mn;}inlineintmax()const{returnmx;}intfind_next(intkey)const{if(key<=min())returnmin();intpos=key>>shift;if(((map>>pos)&1)&&mask(key)<=chd[pos].max()){return(pos<<shift)+chd[pos].find_next(mask(key));}intnxt=ctz(map&~((1ULL<<(pos+1))-1));if(pos==63||nxt==-1)return-1;return(nxt<<shift)+chd[nxt].min();}intfind_prev(intkey)const{if(max()<key)returnmax();intpos=key>>shift;if(((map>>pos)&1)&&chd[pos].min()<mask(key)){return(pos<<shift)+chd[pos].find_prev(mask(key));}intnxt=clz(map&((1ULL<<pos)-1ULL));if(nxt==-1)return-1;return(nxt<<shift)+chd[nxt].max();}};template<intLOG>structw_ary_tree_node<LOG,typenamestd::enable_if<LOG==1>::type>{u64map;w_ary_tree_node():map(0){}voidinsert(intkey){map|=1ULL<<key;}voiderase(intkey){map&=~(1ULL<<key);}boolcontain(intkey)const{return(map>>key)&1;}intmin()const{returnctz(map);}intmax()const{returnclz(map);}intfind_next(intkey)const{returnctz(map&~((1ULL<<key)-1));}intfind_prev(intkey)const{returnclz(map&((1ULL<<key)-1));}};}// namespace w_ary_tree_impltemplate<intLOG=4>usingw_ary_tree=w_ary_tree_impl::w_ary_tree_node<LOG>;/**
* @brief 64-ary tree
*/