/* vectorの配列を吐き出す関数はvfillと同じ要領で簡潔に書けそう だけど面倒 vfillの範囲指定をできるようにしたい */ //#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags //#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX //#pragma GCC target("avx") //Enable AVX #pragma GCC optimize("Ofast") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll=int_fast64_t; using u64=uint_fast64_t; using pii=pair; using pil=pair; using pli=pair; using pll=pair; using psi=pair; using pis=pair; using psl=pair; using pls=pair; using pss=pair; //辺 fromあり template struct Edge { int from, to; T cost; Edge()=default; Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {} inline bool operator<(const Edge p)const noexcept{ return cost(const Edge p)const noexcept{ return cost>p.cost; } }; //辺 fromがない template struct edge { int to; T cost; edge()=default; edge(int _to, T _cost) : to(_to), cost(_cost) {} }; template using edges=vector>; template using WeightGraph=vector>; using Graph=vector>; templateinline constexpr bool chmin(T&a,const U b){if(a<=b)return false;a=b;return true;} templateinline constexpr bool chmax(T&a,const U b){if(a>=b)return false;a=b;return true;} #define bit(n,k) ( ( (n)>>(k) )&1 ) inline void bin101(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout< inline void vin1(vector &v){ for(size_t i=1;i>v[i]; } //0-indexed vector cin template inline void vin0(vector &v){ for(size_t i=0;i>v[i]; } //1-indexed vector cin template inline void vin1(vector> &v){ for(size_t i=1;i>v[i][j]; } } //0-indexed vector cin template inline void vin0(vector> &v){ for(size_t i=0;i>v[i][j]; } } bool DEBUG_MODE=false; #define debug(a) if(DEBUG_MODE){cout<<#a;PRINT(a);cout<void PRINT(const T x){cout<<":"< void PRINT(const vector &v,int a=-1){ if(!DEBUG_MODE) return; cout<<":1d\n"; for(size_t i=0;i void PRINT(const vector> &v,int a=-1,int b=-1){ if(!DEBUG_MODE) return; cout<<":2d\n"; for(size_t i=0;i void PRINT(const vector>> &v,int a=-1,int b=-1,int c=-1){ if(!DEBUG_MODE) return; cout<<":3d\n"; for(size_t i=0;i void PRINT(const vector>>> &v,int a=-1,int b=-1,int c=-1,int d=-1){ if(!DEBUG_MODE) return; cout<<":4d\n"; for(size_t i=0;i void PRINT(const vector>>>> &v,int a=-1,int b=-1,int c=-1,int d=-1,int e=-1){ if(!DEBUG_MODE) return; cout<<":5d\n"; for(size_t i=0;i void PRINT(const set &S){ if(!DEBUG_MODE) return; int now=0; for(auto x:S){ cout< void PRINT(const map &M){ if(!DEBUG_MODE) return; cout<<":map\n"; size_t now=0; for(auto &x:M){ cout< void GPRINT(const vector &v,int a=-1){ if(!DEBUG_MODE) return; cout<<":1d\n"; for(size_t i=0;i void GPRINT(const vector> &v,int a=-1,int b=-1){ if(!DEBUG_MODE) return; cout<<":2d\n"; for(size_t i=0;i inline ostream &operator<<(ostream &os,const pair &p) { os< inline istream &operator>>(istream &is,pair &p) { is>>p.first>>p.second; return is; } //ソート template inline void vsort(vector &v){ sort(v.begin(),v.end()); } //逆順ソート template inline void rvsort(vector &v){ sort(v.rbegin(),v.rend()); } //要素数n 初期値x template inline vector vmake(size_t n,T x){ return vector(n,x); } //a,b,c,x data[a][b][c] 初期値x template auto vmake(size_t n,Args... args){ auto v=vmake(args...); return vector(n,move(v)); } template inline void vfill(T &t,const X... x){ t=T(x...); } template void vfill(vector &t,const X... x){ for(auto &s:t) vfill(s,x...); } //最後に改行があるので注意 template void vout(const vector &v,string s=" ",size_t f=0,int t=-1){ for(size_t i=f;i void vout(const vector> &v,string s=" ",int fh=0,int th=-1,int fw=0,int tw=-1){ for(size_t i=fh;i>n>>h; for(int i=0;i>t; cout<