#include #include using namespace std; namespace my{ #define eb emplace_back #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define jo(a,b) a##b #define FO_IMPL(n,c) for(ll jo(_i,c)=n;jo(_i,c)-->0;) #define FO(n) FO_IMPL(n,__COUNTER__) #define FOR(i,...) for(auto[i,i##stop,i##step]=range(0,__VA_ARGS__);i=i##stop;i+=i##step) #define fe(a,e,...) for(auto&&__VA_OPT__([)e __VA_OPT__(,__VA_ARGS__]):a) #define maybe(p,c) (p?c:remove_cvref_t{}) #define base_operator(op,type) auto operator op(const type&v)const{auto copy=*this;return copy op##=v;} #define entry void solve();void solve2();}int main(){my::io();my::solve();}namespace my{ void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<>{a...});} templatestruct pair{ A a;B b; pair()=default; pair(A a,B b):a(a),b(b){} pair(const std::pair&p):a(p.first),b(p.second){} auto operator<=>(const pair&)const=default; pair operator+(const pair&p)const{return{a+p.a,b+p.b};} friend istream&operator>>(istream&i,pair&p){return i>>p.a>>p.b;} friend ostream&operator<<(ostream&o,const pair&p){return o<using pack_back_t=tuple_element_t>; 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<ostream&operator<<(ostream&o,const vector&v){ll n=v.size();fo(i,n)o<struct 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;} vec&operator+=(const C&c){fe(*this,e)e+=c;return*this;} vec&operator*=(const C&c){fe(*this,e)e*=c;return*this;} base_operator(^,vec) base_operator(+,vec) base_operator(-,vec) base_operator(+,C); base_operator(*,C); vec&operator++(){fe(*this,e)++e;return*this;} vec&operator--(){fe(*this,e)--e;return*this;} ll size()const{return vector::size();} auto&emplace_back(auto&&...a){vector::emplace_back(std::forward(a)...);return*this;} auto scan(const auto&f)const{ pairr{}; fe(*this,e)if constexpr(!vectorial)r.b?f(r.a,e),r:r={e,1};else if(auto s=e.scan(f);s.b)r.b?f(r.a,s.a),r:r=s; return r; } auto max()const{return scan([](auto&a,auto b){if(ares; fo(i,size())if((*this)[i]==x)res.eb(i); return res; } }; templaterequires(sizeof...(A)>=2)vec(const A&...a)->vec>>; vec(ll)->vec; void lin(auto&...a){(cin>>...>>a);} auto sin(){string s;lin(s);return s;} templateauto sinen(const string&b){vecr;fe(sin(),e)r.eb(b.find_first_of(e));return r;} templateauto sinen(ll n,const string&b){vec>r;fo(n)r.eb(sinen(b));return r;} void pp(const auto&...a){ll n=sizeof...(a);((cout<0,space)),...);cout<