#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("inline") #pragma GCC diagnostic ignored "-Wunused-value" #include using namespace std; /* * Additional Type Definition */ using ll=long long; using ld=long double; using ull=unsigned long long; using vb=vector; using vvb=vector; using vd=vector; using vvd=vector; using vi=vector; using vvi=vector; using vl=vector; using vvl=vector; using pii=pair; using pll=pair; using vp=vector; using tl2=tuple; using tl3=tuple; using vs=vector; #define all(a) begin(a),end(a) #define rall(a) rbegin(a),rend(a) #define __LOOPSWITCH(_1, _2, _3, __LOOPSWITCH, ...) __LOOPSWITCH #define rep(...) __LOOPSWITCH(__VA_ARGS__, __RANGE, __REP, __LOOP) (__VA_ARGS__) #define rrep(...) __LOOPSWITCH(__VA_ARGS__, __RRANGE, __RREP, __LOOP) (__VA_ARGS__) #define __LOOP(q) __LOOP2(q, __LINE__) #define __LOOP2(q,l) __LOOP3(q,l) #define __LOOP3(q,l) __REP(_lp ## l,q) #define __REP(i,n) __RANGE(i,0,n) #define __RANGE(i,a,n) for(ll i=((ll)a);i<((ll)n);++i) #define __RREP(i,n) __RRANGE(i,0,n) #define __RRANGE(i,a,n) for(ll i=((ll)(n)-1);i>=((ll)a);--i) #define sz(a) ((ll)(a).size()) /* * Constants */ constexpr ll LINF=1ll<<60; constexpr int INF=1<<30; constexpr double EPS=(1e-14); constexpr ll MOD=998244353ll; constexpr long double PI=3.14159265358979323846; /* * Utilities */ templateconstexpr bool chmax(T&a,T b){return aconstexpr bool chmin(T&a,T b){return a>b?a=b,1:0;} templateS sum(vector&a){return accumulate(all(a),S());} templateS max(vector&a){return *max_element(all(a));} templateS min(vector&a){return *min_element(all(a));} namespace IO { // container detection template struct is_container : false_type {}; template<> struct is_container : false_type {}; template struct is_container_helper {}; template struct is_container().size()), decltype(declval().begin()), decltype(declval().end()) >>> : public true_type {}; template{}, nullptr_t>::type = nullptr, char Separator = is_container{} ? '\n' : ' ' > constexpr ostream&operator<<(ostream&os, T t){ if(auto b=begin(t), e=end(t) ; !t.empty()) for(os<<(*b++);b!=e;os< constexpr ostream& pargs(ostream&os, T&&t, Ts&&...args); // support clang templateconstexpr ostream&operator<<(ostream&os,pairp){ return os<<'['<constexpr ostream&operator<<(ostream&os,tuplet){ return apply([&os](auto&&t,auto&&...args)->ostream&{return pargs(os, t, args...);}, t); }; template constexpr ostream& pargs(ostream&os, T&&t, Ts&&...args) { return ((os< constexpr ostream& out(Ts...args) { return pargs(cout, args...)<<'\n'; } template constexpr ostream& debug_f(Ts...args) { return pargs(cerr, args...)<<'\n'; } #ifdef _DEBUG template constexpr ostream& debug(Ts...args) { return pargs(cerr, args...)<<'\n'; } #else #define debug(...) if(false)debug_f(__VA_ARGS__) #endif void Yn(bool f) { out(f?"Yes":"No"); } // input template constexpr istream& gargs(istream&is, T&&t, Ts&&...args) { return ((is>>t)>>...>>args); } templateauto&operator>>(istream&is,pair&p){return is>>p.first>>p.second;} templateconstexpr istream&operator>>(istream&is,tuple&t){ return apply([&is](auto&&t,auto&&...args)->istream&{return gargs(is, t, args...);}, t); }; templateauto&in(S&...s){return gargs(cin, s...);} #define def(t,...) t __VA_ARGS__; in(__VA_ARGS__) template{}, nullptr_t>::type = nullptr> auto&operator>>(istream&is,T&t){for(auto&a:t)is>>a; return is;} } using namespace IO; class Random { public: typedef uint_fast32_t result_type; constexpr result_type operator()(){return operator()((ll)min(),(ll)max());} static constexpr result_type max(){return numeric_limits::max();} static constexpr result_type min(){return 0;} constexpr Random(const bool&isDeterministic):y(isDeterministic?2463534242:chrono::system_clock::now().time_since_epoch().count()){} constexpr int operator()(int a,int b){return next()%(b-a)+a;} constexpr ll operator()(ll a,ll b){return (((ull)next())<<32|next())%(b-a)+a;} constexpr double operator()(double a,double b){return (b-a)*next()/4294967296.0+a;} private: result_type y; constexpr result_type next(){return y^=(y^=(y^=y<<13)>>17)<<5;} } Random(0); class Timer { #ifdef _DEBUG static constexpr uint64_t ClocksPerMsec = 3587000; #else static constexpr uint64_t ClocksPerMsec = 2987000; #endif const uint64_t start,limit; uint64_t getClocks() const{ unsigned int lo,hi; __asm__ volatile ("rdtsc" : "=a" (lo), "=d" (hi)); return((uint64_t)hi<<32)|lo; } public: Timer(uint64_t _limit=1970): start(getClocks()),limit(start+_limit*ClocksPerMsec) {} uint64_t get() const{return (getClocks()-start)/ClocksPerMsec;} operator bool()const{return getClocks()> q; q.emplace(init,0); while(!q.empty()){ auto [s,mScore]=q.front(); q.pop(); out(s)<