#include #include using namespace std; namespace my{ #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define FO(n) for(ll ij=n;ij-->0;) #define FOR(i,...) for(auto[i,i##stop,i##step]=range(0,__VA_ARGS__);i{}) #define base_operator(op,type) auto operator op(const type&v)const{auto copy=*this;return copy op##=v;} #define single_testcase void solve();}int main(){my::io();my::solve();}namespace my{ void io(){cerr<sync_with_stdio(0);cout<>(istream&i,ulll&x){ull t;i>>t;x=t;return i;} ostream&operator<<(ostream&o,const ulll&x){return(x<10?o:o<>(istream&i,lll&x){ll t;i>>t;x=t;return i;} ostream&operator<<(ostream&o,const lll&x){return o<<(x<0?"-":"")<0?x:-x);} constexpr auto range(ll s,ll b){ll a=0;if(s)swap(a,b);return array{a-s,b,1-s*2};} constexpr auto range(ll s,ll a,ll b,ll c=1){return array{a-s,b,(1-s*2)*c};} const string newline{char(10)}; const string space{char(32)}; constexpr auto abs(auto x){return x<0?-x:x;} constexpr auto pow(lll x,ll n){assert(n>=0);lll r=1;while(n)n&1?r*=x:r,x*=x,n>>=1;return r;} constexpr ll size10(auto x){x|=1;ll r=0;while(x>0)x/=10,++r;return r;} bool amin(auto&a,const auto&b){return b>{a...});} templatestruct infinity{ templateconstexpr operator T()const{return(pow(10,size10(numeric_limits::max()))-1)/9*(1-is_negative*2);} templateconstexpr operator T()const{return static_cast(*this);} templateconstexpr bool operator==(T x)const{return static_cast(*this)==x;} constexpr auto operator-()const{return infinity();} }; constexpr infinity oo; templateconcept vectorial=is_base_of_v::value_type>,remove_cvref_t>; templateconstexpr int rank(){if constexpr(vectorial)return rank()+1;else return 0;} templatestruct core_t_helper{using core_t=T;}; templatestruct core_t_helper{using core_t=typename core_t_helper::core_t;}; templateusing core_t=core_t_helper::core_t; templateistream&operator>>(istream&i,vector&v){fe(v,e)i>>e;return i;} templateostream&operator<<(ostream&o,const vector&v){ll n=v.size();fo(i,n)o<?newline:space);return o;} templatestruct vec; templatestruct hvec_helper{using type=vec::type>;}; templatestruct hvec_helper<0,T>{using type=T;}; templateusing hvec=typename hvec_helper::type; templatestruct vec:vector{ static constexpr int R=rank>(); using C=core_t; using vector::vector; vec(const vector&v){vector::operator=(v);} vec(const auto&...a)requires(sizeof...(a)>=3){resizes(a...);} void resizes(const auto&...a){*this=make(a...);} static auto make(ll n,const auto&...a){if constexpr(sizeof...(a)==1)return vec(n,array{a...}[0]);else return vec(n,make(a...));} vec&operator^=(const vec&u){this->insert(this->end(),u.begin(),u.end());return*this;} vec&operator+=(const vec&u){vec&v=*this;assert(v.size()==u.size());fo(i,v.size())v[i]+=u[i];return v;} vec&operator-=(const vec&u){vec&v=*this;assert(v.size()==u.size());fo(i,v.size())v[i]-=u[i];return v;} base_operator(^,vec) base_operator(+,vec) base_operator(-,vec) vec&operator++(){fe(*this,e)++e;return*this;} vec&operator--(){fe(*this,e)--e;return*this;} ll size()const{return vector::size();} auto transform(const auto&f)const{ hvecres(size()); if constexpr(vectorial)fo(i,size())res[i]=(*this)[i].transform(f); else std::transform(this->begin(),this->end(),res.begin(),f); return res; } vec abs()const{return transform([](const auto&e){return e<0?-e:e;});} }; void lin(auto&...a){(cin>>...>>a);} void pp(const auto&...a){ll n=sizeof...(a);((cout<0,space)),...);cout<