#include #include using namespace atcoder; using namespace std; #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define fin(...) return pt(__VA_ARGS__) #define eb(...) emplace_back(__VA_ARGS__) #define ef(...) emplace_front(__VA_ARGS__) #define elif(...) else if(__VA_ARGS__) #define overload4(a,b,c,d,e,...) e #define rep1(b) for(ll _i=0;_i<(ll)(b);_i++) #define rep2(i,b) for(ll i=0;i<(ll)(b);i++) #define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c)) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(a) for(ll _i=(ll)(a);_i>=0;_i--) #define rrep2(i,a) for(ll i=(ll)(a);i>=0;i--) #define rrep3(i,a,b) for(ll i=(ll)(a);i>=(ll)(b);i--) #define rrep4(i,a,b,c) for(ll i=(ll)(a);i>=(ll)(b);i-=(ll)(c)) #define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;lin(__VA_ARGS__) using ll=long long; using ld=long double; using v1=vector; using v2=vector; using v3=vector; using v4=vector; using pll=pair; using mll=map; using mint=modint998244353; ll inf=3e18; ld pi=acosl(-1); ld eps=1e-10; templatell sgn(const T&a){return(a>eps)-(a<-eps);} templatell sgn(const T&a,const T&b){return sgn(a-b);} templatevector&operator++(vector&v){for(T&x:v)x++;return v;} templatevector&operator--(vector&v){for(T&x:v)x--;return v;} templatevector operator++(vector&v,int){vectorr=v;++v;return r;} templatevector operator--(vector&v,int){vectorr=v;--v;return r;} templateusing max_priority_queue=std::priority_queue; templateusing min_priority_queue=std::priority_queue,greater>; templatebool chmax(T&a,const U&b){return abool chmin(T&a,const U&b){return a>b?a=b,1:0;} templateT max(const vector&a){return *max_element(all(a));} templateT min(const vector&a){return *min_element(all(a));} templateconstexpr auto max(T...a){return max(initializer_list>{a...});} templateconstexpr auto min(T...a){return min(initializer_list>{a...});} templateT gcd(const T&a,const A&...b){return gcd(a,gcd(b...));} templateT sum(const vector&a){return accumulate(all(a),T(0));} templateT popcnt(T a){return __builtin_popcountll(a);} templatell lbp(const vector&a,const T&b){return lower_bound(all(a),b)-a.begin();} templatell ubp(const vector&a,const T&b){return upper_bound(all(a),b)-a.begin();} templatepairmima(const T&a,const T&b){return{min(a,b),max(a,b)};} templatepairmima(const pair&p){auto[a,b]=p;return mima(a,b);} templateT at(const vector&v,const ll&i){ll n=v.size();return v[(i%n+n)%n];} templatevoid sort(vector&v){sort(all(v));} templatevoid sort(vector&v,const F&f){sort(all(v),f);} templatevoid rev(vector&v){reverse(all(v));} templatevoid uni(vector&v){sort(all(v));v.erase(unique(all(v)),v.end());} void sort(string&s){sort(all(s));} void rev(string&s){reverse(all(s));} v1 iota(ll n,ll s=0){v1 a(n);iota(all(a),s);return a;} void emplace_front(v1&v,ll x=0){v.emplace(v.begin(),x);} struct fast_ios{fast_ios(){cin.tie(nullptr);ios::sync_with_stdio(false);cout<>(istream&is,mint&x){ll t;is>>t;x=t;return is;} ostream&operator<<(ostream&os,const mint&x){return os<istream&operator>>(istream&is,pair&p){return is>>p.first>>p.second;} templateostream&operator<<(ostream&os,const pair&p){return os<istream&operator>>(istream&is,vector&v){for(T&x:v)is>>x;return is;} templateostream&operator<<(ostream&os,const vector&v){rep(i,v.size())os<ostream&operator<<(ostream&os,const vector>&v){rep(i,v.size())os<ostream&operator<<(ostream&os,const set&v){for(auto&x:v)os<ostream&operator<<(ostream&os,const map&m){for(auto&[k,v]:m)os<first)?"":"\n");return os;} templateostream&operator<<(ostream&os,const tuple&t){return os<(t)<<" "<(t)<<" "<(t);} ll pt(){cout<ll pt(const T&a,const A&...b){cout<ll db(const T&a,const A&...b){cerr<void lin(T&a){cin>>a;} templatevoid lin(T&...a){(cin>>...>>a);} templatevoid vin(const ll k,vector&...a){(cin>>...>>a[k]);} templatevoid vin(vector&a,A&...b){rep(i,a.size())vin(i,a,b...);} templatevoid resize(vector&v,const T&a){v.resize(a);} templatevoid resize(vector&vv,const T&a,const A&...b){vv.resize(a);for(V&v:vv)resize(v,b...);} templatevoid fill(V&v,const T&x){v=x;} templatevoid fill(vector&vv,const T&x){for(V&v:vv)fill(v,x);} void com(v1&v,v1&h){for(ll&x:h)x=lbp(v,x);} templatevoid com(v1&v,v1&h,T&...t){for(ll&x:h)x=lbp(v,x);com(v,t...);} templatev1 compress(T&...a){v1 v;for(auto&e:{a...})copy(all(e),back_inserter(v));uni(v);com(v,a...);return v;} templateT binsearch(functionj,T ok,T ng){T D=(*typeid(ok).name()=='x'?1:eps);while(abs(ok-ng)>D){T m=(ok+ng)/2;(j(m)?ok:ng)=m;}return ok;} v1 divisor(ll n){mll m;for(ll i=1;i*i<=n;i++){if(n%i==0){m[i]++;m[n/i]++;}}v1 v;for(auto[x,_]:m)v.eb(x);return v;} mll factor(ll n){mll m;for(ll i=2;i*i<=n;i++){while(n%i==0){m[i]++;n/=i;}}if(n>1)m[n]++;return m;} ll mpow(ll x,ll n,ll m=0){ll r=1;while(n>0){if(n&1){r*=x;if(m)r%=m;}x*=x;if(m)x%=m;n>>=1;}return r;} ll minv(ll a,ll m){ll b=m,u=1,v=0;while(b){ll t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}u%=m;if(u<0)u+=m;return u;} ll lsqrt(ll x){ll r=sqrtl(x)-1;while(r+1<=x/(r+1))r++;return r;} ll llog2(ll n){ll r=0;while(n){n>>=1;r++;}return r;} mint mhash(mint a){return a*(a+1346)*(a+9185);} ll bit(ll n){return 1LL<