#include #include using namespace atcoder; using namespace std; #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define fin(a) return pt(a) #define rep(i,n) for(ll i=0;i<(ll)(n);i++) 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; ll inf=3e18; ld pi=acos(-1); ld eps=1e-10; templateusing max_priority_queue=std::priority_queue; templateusing min_priority_queue=std::priority_queue,greater>; templatebool chmax(T&a,const T&b){return abool chmin(T&a,const T&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));} 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();} templatepll mima(const T&a,const T&b){return {min(a,b),max(a,b)};} 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 usort(vector&v){sort(all(v));v.erase(unique(all(v)),v.end());} ostream&operator<<(ostream&os,const modint1000000007&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){for(ll i=0;i<(ll)v.size();i++)os<ll pt_rest(){cout<<'\n';return 0;} templatell pt(){cout<<'\n';return 0;} templatell pt_rest(const T&first,const A&...rest){cout<<" "<ll pt(const T&first,const A&...rest){cout<void resize(vector&vec,const H head){vec.resize(head);} templatevoid resize(vector&vec,const H&head,const T...tail){vec.resize(head);for(auto&v:vec)resize(v,tail...);} templatevoid fill(V&x,const T&val){x=val;} templatevoid fill(vector&vec,const T&val){for(auto&v:vec)fill(v,val);} templatevoid vin(istream&is,const ll idx,vector&head){is>>head[idx];} templatevoid vin(istream&is,const ll idx,vector&head,T&...tail){vin(is>>head[idx],idx,tail...);} templatevoid vin(istream&is,vector&head,T&...tail){for(ll i=0;i<(ll)head.size();i++)vin(is,i,head,tail...);} templatevoid vin(vector&head,T&...tail){vin(cin,head,tail...);} templatevoid sin(istream&is,H&head){is>>head;} templatevoid sin(istream&is,H&head,T&...tail){sin(is>>head,tail...);} templatevoid sin(H&head,T&...tail){sin(cin,head,tail...);} templatevoid printv2(vector>&a){for(ll i=0;i1)m[n]++;return m;} ll lpow(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 lsqrt(ll x){assert(x>=0);if(x<=1)return x;ll r=sqrt(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;} ll bit(ll n){return 1LL<>N; for(ll i=0;i