#pragma GCC optimize ("O3,Ofast,inline,fast-math,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
#define int int64_t
#define double long double
#define INIT std::ios_base::sync_with_stdio(0);std::cin.tie(0);std::cout<<std::fixed<<std::setprecision(15);
#define WRITE_FUNCTION_UNDER_HERE DEFALLTYPE(VDEF)DEFALLTYPE(PDEF3)
const int MOD=1e9+7;
using namespace std;const int MAX=std::numeric_limits<int>::max();const int MIN=std::numeric_limits<int>::min();const double EPS=1e-7;
#define fou(i,a,n) for(int i=a;i<n;i++)
#define fod(i,a,n) for(int i=n-1;i>=a;i--)
#define tra(e,v) for(auto&e:v)
#define elif(c) else if(c)
#define fi first
#define se second
#define fir fi
#define sec se.fi
#define thi se.se
#define firs fi
#define seco sec
#define thir thi.fi
#define four thi.se
#define DEFALLTYPE(XDEF) XDEF(int,I)XDEF(double,D)XDEF(char,C)XDEF(String,S)XDEF(bool,B)XDEF(Modulo,M)
#define VDEF(t,T) typedef Vector<t>V##T;typedef Vector<V##T>VV##T;typedef Vector<VV##T>VVV##T;
#define PDEF(x,X,y,Y,z,Z,w,W) typedef std::pair<x,y>P##X##Y;VDEF(P##X##Y,P##X##Y)typedef std::pair<x,std::pair<y,z>>P##X##Y##Z;VDEF(P##X##Y##Z,P##X##Y##Z)typedef std::pair<x,std::pair<y,std::pair<z,w>>>P##X##Y##Z##W;VDEF(P##X##Y##Z##W,P##X##Y##Z##W)
#define PDEF1(y,Y,z,Z,w,W) PDEF(int,I,y,Y,z,Z,w,W)PDEF(double,D,y,Y,z,Z,w,W)PDEF(char,C,y,Y,z,Z,w,W)PDEF(String,S,y,Y,z,Z,w,W)PDEF(bool,B,y,Y,z,Z,w,W)PDEF(Modulo,M,y,Y,z,Z,w,W)
#define PDEF2(z,Z,w,W) PDEF1(int,I,z,Z,w,W)PDEF1(double,D,z,Z,w,W)PDEF1(char,C,z,Z,w,W)PDEF1(String,S,z,Z,w,W)PDEF1(bool,B,z,Z,w,W)PDEF1(Modulo,M,z,Z,w,W)
#define PDEF3(w,W) PDEF2(int,I,w,W)PDEF2(double,D,w,W)PDEF2(char,C,w,W)PDEF2(String,S,w,W)PDEF2(bool,B,w,W)PDEF2(Modulo,M,w,W)

// in, out
#define in(T,...) T __VA_ARGS__;_in(__VA_ARGS__)
void _in(){}template<typename Hd,typename...Tl>void _in(Hd&hd,Tl&&...tl){std::cin>>hd;_in(std::forward<Tl>(tl)...);}void out(){std::cout<<'\n';}template<typename T>void out(const T&a){std::cout<<a<<'\n';}template<typename Hd,typename ...Tl>void out(const Hd&hd,const Tl&...tl){std::cout<<hd<<' ';out(tl...);}

// std::pair io,calc
#define PairCalc(OP) template<typename T,typename U,typename V,typename W>std::pair<T,U>operator OP(const std::pair<T,U>&l,const std::pair<V,W>&r){return std::make_pair(l.first OP r.first,l.second OP r.second);}template<typename T,typename U,typename V,typename W>std::pair<T,U>operator OP##=(std::pair<T,U>&l,const std::pair<V,W>&r){return l=l OP r;}
template<typename T,typename U>std::istream&operator>>(std::istream&i,std::pair<T,U>&p){i>>p.first>>p.second;return i;}template<typename T,typename U>std::ostream&operator<<(std::ostream&o,const std::pair<T,U>&p){return o<<p.first<<' '<<p.second;}PairCalc(+)PairCalc(-)PairCalc(*)PairCalc(/)PairCalc(%)PairCalc(<<)PairCalc(>>)PairCalc(&)PairCalc(|)PairCalc(^)template<typename T,typename U>std::pair<T,U>mp(const T&t,const U&u){return std::make_pair(t,u);}template<typename T,typename U,typename V>std::pair<T,std::pair<U,V>>mp(const T&t,const U&u,const V&v){return std::make_pair(t,std::make_pair(u,v));}template<typename T,typename U,typename V,typename W>std::pair<T,std::pair<U,std::pair<V,W>>>mp(const T&t,const U&u,const V&v,const W&w){return std::make_pair(t,std::make_pair(u,std::make_pair(v,w)));}

// Vector class
#define VecCalc(OP) VT operator OP(const VT&r)const{VT v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=(*this)[i]OP r[i];return v;}VT operator OP(const T&r)const{VT v(size());for(int i=0;i<size();i++)v[i]=(*this)[i]OP r;return v;}VT operator OP##=(const VT&r){return *this=*this OP r;}VT operator OP##=(const T&r){return *this=*this OP r;}
#define VecComp(OP) Vector<int>operator OP(const VT&r)const{Vector<int>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=(*this)[i]OP r[i];return v;}Vector<int>operator OP(const T&r)const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=(*this)[i]OP r;return v;}
#define VVCalc(OP) template<typename T,typename U>Vector<Vector<T>>operator OP(Vector<Vector<T>>l,const U&r){for(Vector<T>&e:l)e OP##=r;return l;}template<typename T,typename U>Vector<Vector<T>>operator OP##=(Vector<Vector<T>>&l,const U&r){return l=l OP r;}
#define VVComp(OP) template<typename T,typename U>Vector<Vector<int>>operator OP(const Vector<Vector<T>>&l,const U&r){Vector<Vector<int>>v(l.size());for(int i=0;i<l.size();i++)v[i]=l[i] OP r;return v;}
template<typename T>class Vector:public std::vector<T>{public:typedef std::vector<T>SVT;typedef Vector<T>VT;using SVT::operator[];using SVT::operator=;using SVT::begin;using SVT::end;using SVT::rbegin;using SVT::rend;using SVT::resize;using SVT::assign;using SVT::push_back;using SVT::pop_back;Vector(const SVT&v):SVT(v){}Vector(int s=0,T v=T()){if(s>=0)assign(s,v);else{assign(-s,v);for(T&e:*this)std::cin>>e;}}Vector(const std::initializer_list<T>&l):SVT(l){}template<typename U>Vector(const std::vector<U>&v){for(const T&e:v)pub(e);}template<typename U>Vector(const __gnu_pbds::tree<U,__gnu_pbds::null_type,std::less<U>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>&t){for(const T&e:t)pub(e);}template<typename U>Vector(const __gnu_cxx::rope<U>&r){for(const T&e:r)pub(e);}Vector(const std::string&s){for(const T&e:s)pub(e);}int size()const{return SVT::size();}
VT operator[](const std::initializer_list<int>&l)const{if(l.size()==2||l.size()==3){int first=*l.begin(),last=*(l.begin()+1),step=(l.size()==2?1:*(l.begin()+2));last=(last<0?last+size()+1:last);VT v;for(int i=first;i<last;i+=step)v.pub((*this)[i]);return v;}return *this;}VT operator+()const{return *this;}VT operator-()const{VT v(size());for(int i=0;i<size();i++)v[i]=-(*this)[i];return v;}VT operator++(){for(T&e:*this)e++;return *this;}VT operator--(){for(T&e:*this)e--;return *this;}VT operator++(int32_t){VT v=*this;for(T&e:*this)e++;return v;}VT operator--(int32_t){VT v=*this;for(T&e:*this)e--;return v;}void out(){for(const T&e:*this)std::cout<<e<<'\n';}void outstr(){for(int i=0;i<size()-1;i++)std::cout<<(*this)[i];std::cout<<last()<<'\n';}void iota(){for(int i=0;i<size();i++)(*this)[i]=i;}T last()const{return (*this)[size()-1];}T&last(){return (*this)[size()-1];}
T sum(int l=0,int r=-1)const{T v=T();r=(r<0?r+size()+1:r);for(int i=l;i<r;i++)v+=(*this)[i];return v;}T prod(int l=0,int r=-1)const{T v=T()+1;r=(r<0?r+size()+1:r);for(int i=l;i<r;i++)v*=(*this)[i];return v;}T xorsum(int l=0,int r=-1)const{T v=T();r=(r<0?r+size()+1:r);for(int i=l;i<r;i++)v^=(*this)[i];return v;}int argmin()const{return std::min_element(begin(),end())-begin();}int argmax()const{return std::max_element(begin(),end())-begin();}T min()const{return(*this)[argmin()];}T max()const{return(*this)[argmax()];}T dot(const VT&v)const{T r=T();for(int i=0;i<std::min(size(),v.size());i++)r+=(*this)[i]*v[i];return r;}void pub(const T&v){SVT::push_back(v);}void pub(const VT&v){SVT::insert(end(),v.begin(),v.end());}void insert(int i,const T&v){SVT::insert(begin()+i,v);}void insert(int i,const VT&v){SVT::insert(begin()+i,v.begin(),v.end());}void pob(){pop_back();}void erase(int i){SVT::erase(begin()+i);}void erase(int i,int j){SVT::erase(begin()+i,begin()+j);}void erase_unique(){SVT::erase(std::unique(begin(),end()),end());}void reverse(){std::reverse(begin(),end());}void rotatedown(int i){if(i>0)std::rotate(begin(),begin()+i,end());}void rotateup(int i){if(i>0)std::rotate(rbegin(),rbegin()+i,rend());}void sortup(){std::sort(begin(),end());}void sortdown(){std::sort(rbegin(),rend());}
void cumsum(){for(int i=0;i<size()-1;i++)(*this)[i+1]+=(*this)[i];}void decumsum(){for(int i=size()-2;i>=0;i--)(*this)[i+1]-=(*this)[i];}T cumsumpart(int l,int r)const{return(*this)[r-1]-(l=0?0:(*this)[l-1]);}void cumxor(){for(int i=0;i<size()-1;i++)(*this)[i+1]^=(*this)[i];}void decumxor(){for(int i=size()-2;i>=0;i--)(*this)[i+1]^=(*this)[i];}T cumxorpart(int l,int r)const{return(*this)[r-1]^(l=0?0:(*this)[l-1]);}void bucketsortup(){int m=min();Vector<int>b(max()-m+1);for(int e:(*this))b[e-m]++;b.cumsum();for(int i=0;i<b.size();i++)for(int j=(i==0?0:b[i-1]);j<b[i];j++)(*this)[j]=m+i;}void bucketsortdown(){bucketsortup();reverse();}void compress(){VT u(*this);u.sortup();u.erase_unique();std::unordered_map<T,int>m;for(int i=0;i<u.size();i++)m[u[i]]=i;for(int i=0;i<size();i++)(*this)[i]=m[(*this)[i]];}
int findgeq(const T&v){if(size()==0)return 0;if((*this)[0]<=last())return std::lower_bound(begin(),end(),v)-begin();else return size()-(std::lower_bound(rbegin(),rend(),v)-rbegin())-1;}int findleq(const T&v){if(size()==0)return 0;if((*this)[0]<=last())return std::upper_bound(begin(),end(),v)-begin()-1;else return size()-(std::upper_bound(rbegin(),rend(),v)-rbegin());}int countleq(const T&v){if(size()==0)return 0;if((*this)[0]<=last())return std::upper_bound(begin(),end(),v)-begin();else return std::upper_bound(rbegin(),rend(),v)-rbegin();}int countgeq(const T&v){if(size()==0)return 0;if((*this)[0]<=last())return size()-(std::lower_bound(begin(),end(),v)-begin());else return size()-(std::lower_bound(rbegin(),rend(),v)-rbegin());}int counteq(const T&v){return abs(findleq(v)-findgeq(v))+1;}VecCalc(+)VecCalc(-)VecCalc(*)VecCalc(/)VecCalc(%)VecCalc(<<)VecCalc(>>)VecCalc(&)VecCalc(|)VecCalc(^)VecComp(==)VecComp(!=)VecComp(>=)VecComp(<=)VecComp(>)VecComp(<)
VT iotaed()const{VT r(*this);r.iota();return r;}VT pubed(const T&v)const{VT r(*this);r.pub(v);return r;}VT pubed(const VT &v)const{VT r(*this);r.pub(v);return r;}VT inserted(int i,const T&v)const{VT r(*this);r.insert(i,v);return r;}VT inserted(int i,const VT &v)const{VT r(*this);r.insert(i,v);return r;}VT pobed()const{VT r(*this);r.pob();return r;}VT erased(int i,int j=-1)const{VT r(*this);r.erase(i,j);return r;}VT erase_uniqued()const{VT r(*this);r.erase_unique();return r;}VT reversed()const{VT r(*this);r.reverse();return r;}VT rotatedowned(int i)const{VT r(*this);r.rotatedown(i);return r;}VT rotateuped(int i)const{VT r(*this);r.rotateup(i);return r;}VT sortuped()const{VT r(*this);r.sortup();return r;}VT sortdowned()const{VT r(*this);r.sortdown();return r;}VT cumsumed()const{VT r(*this);r.cumsum();return r;}VT decumsumed()const{VT r(*this);r.decumsum();return r;}VT cumxored()const{VT r(*this);r.cumxor();return r;}VT decumxored()const{VT r(*this);r.decumxor();return r;}VT bucketsortuped()const{VT r(*this);r.bucketsortup();return r;}VT bucketsortdowned()const{VT r(*this);r.bucketsortdown();return r;}VT compressed()const{VT r(*this);r.compress();return r;}};
VVCalc(+)VVCalc(-)VVCalc(*)VVCalc(/)VVCalc(%)VVCalc(<<)VVCalc(>>)VVCalc(&)VVCalc(|)VVCalc(^)VVComp(==)VVComp(!=)VVComp(>=)VVComp(<=)VVComp(>)VVComp(<)template<typename T,typename U>Vector<std::pair<T,U>>unite(const Vector<T>&v,const Vector<U>&u){int s=std::min(v.size(),u.size());Vector<std::pair<T,U>>r(s);for(int i=0;i<s;i++)r[i]=std::make_pair(v[i],u[i]);return r;}template<typename T,typename U>std::pair<Vector<T>,Vector<U>>separate(const Vector<std::pair<T,U>>&p){Vector<T>v(p.size());Vector<U>u(p.size());for(int i=0;i<p.size();i++){v[i]=p[i].first;u[i]=p[i].second;}return std::make_pair(v,u);}template<typename T>std::istream&operator>>(std::istream&i,std::vector<T>&v){for(T&e:v)i>>e;return i;}template<typename T>std::ostream&operator<<(std::ostream&o,const std::vector<T>&v){if(v.size()==0)return o;for(int i=0;i<v.size()-1;i++)o<<v[i]<<' ';return o<<v[v.size()-1];}Vector<int>baseVector(int n,int b){Vector<int>v(64);for(int&e:v){e=n%b;n/=b;}return v;}int baseVectorValue(Vector<int>v,int b){int n=0,m=1;for(int&e:v){n+=e*m;m*=b;}return n;}

// Set class
template<typename T>class Set:public __gnu_pbds::tree<T,__gnu_pbds::null_type,std::less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>{public:typedef __gnu_pbds::tree<T,__gnu_pbds::null_type,std::less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>tree;using tree::operator=;using tree::begin;using tree::end;using tree::insert;using tree::erase;using tree::split;Set(const tree&t):tree(t){}Set(int n=0){for(int i=0;i<-n;i++){T v;std::cin>>v;insert(v);}}Set(const std::initializer_list<T>&l){for(const T&e:l)insert(e);}int size()const{return tree::size();}template<typename U>Set(const std::vector<U>&v){for(const T&e:v)insert(e);}template<typename U>Set(const __gnu_pbds::tree<U,__gnu_pbds::null_type,std::less<U>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>&t){for(const T&e:t)insert(e);}template<typename U>Set(const __gnu_cxx::rope<U>&r){for(const T&e:r)insert(e);}Set(const std::string&s){for(const T&e:s)insert(e);}
bool contains(const T&v)const{return tree::find(v)!=end();}void merge(const tree&s){tree t=s;tree::join(t);}int order(const T&v){return tree::order_of_key(v);}int rorder(const T&v){return size()-tree::order_of_key(v)-1;}T operator[](int i)const{return *(tree::find_by_order(i));}std::pair<Set<T>,Set<T>>splitted(const T&v)const{Set<T>s=*this,t;s.split(v,t);return std::make_pair(s,t);}Set<T>&operator<<(const T&v){insert(v);return *this;}Set<T>&operator<<(const tree&s){merge(s);return *this;}Set<T>&operator>>(const T&v){erase(v);return *this;}bool operator>(const T&v){return contains(v);}};template<typename T>std::ostream&operator<<(std::ostream&o,const Set<T>&s){if(s.size()==0)return o;for(int i=0;i<s.size()-1;i++)o<<s[i]<<' ';return o<<s[s.size()-1];}

// Map class
template<typename T,typename U>class Map:public __gnu_pbds::tree<T,U,std::less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>{public:typedef __gnu_pbds::tree<T,U,std::less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>tree;using tree::operator=;using tree::operator[];using tree::begin;using tree::end;using tree::insert;using tree::erase;using tree::split;Map(const tree&t):tree(t){}Map(int n=0){for(int i=0;i<-n;i++){T k;U v;std::cin>>k>>v;insert(k,v);}}Map(std::initializer_list<std::pair<T,U>>l){for(const std::pair<T,U>&e:l)insert(e);}int size()const{return tree::size();}std::pair<T,U>key_value(int i)const{return *tree::find_by_order(i);}void insert(const T&k,const U&v){tree::insert(std::make_pair(k,v));}bool contains(const T&k)const{return tree::find(k)!=end();}void merge(const tree&t){Map<T,U>n=t;tree::join(n);}int order(const T&k){return tree::order_of_key(k);}int rorder(const T&v){return size()-tree::order_of_key(v)-1;}std::pair<Map<T,U>,Map<T,U>>splitted(const T&v)const{Map<T,U>s=*this,t;s.split(v,t);return std::make_pair(s,t);}Map<T,U>&operator<<(const std::pair<T,U>&v){insert(v);return *this;}Map<T,U>&operator<<(const tree&m){merge(m);return *this;}Map<T,U>&operator>>(const T&v){erase(v);return *this;}bool operator>(const T&v){return contains(v);}};template<typename T,typename U>std::ostream&operator<<(std::ostream&o,const Map<T,U>&m){if(m.size()==0)return o;for(int i=0;i<m.size()-1;i++)o<<m.key_value(i).first<<' '<<m.key_value(i).second<<'\n';return o<<m.key_value(m.size()-1).first<<' '<<m.key_value(m.size()-1).second;}

// Rope class
template<typename T>class Rope:public __gnu_cxx::rope<T>{typedef __gnu_cxx::rope<T>rope;public:using rope::replace;using rope::insert;using rope::operator[];using rope::operator=;using rope::begin;using rope::end;using rope::rbegin;using rope::rend;Rope(const rope&r):rope(r){}Rope(int n=0){for(int i=0;i<-n;i++){T v;std::cin>>v;pub(v);}}Rope(const std::initializer_list<T>&l){for(const T&e:l)pub(e);}template<typename U>Rope(const std::vector<U>&v){for(const T&e:v)pub(e);}template<typename U>Rope(const __gnu_pbds::tree<U,__gnu_pbds::null_type,std::less<U>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>&t){for(const T&e:t)pub(e);}template<typename U>Rope(const __gnu_cxx::rope<U>&r){for(const T&e:r)pub(e);}Rope(const std::string&s){for(const T&e:s)pub(e);}int size()const{return rope::size();}void pub(const T&v){insert(size(),v);}void erase(int i){rope::erase(i,1);}void erase(int i,int j){rope::erase(i,j-i);}void pob(){erase(size()-1);}void resize(int s,const T&v=T()){while(s<size())pob();while(s>size())pub(v);}
Rope<T>operator[](const std::initializer_list<int>&l)const{if(l.size()==2)return rope::substr(*l.begin(),*(l.begin()+1)-*l.begin());if(l.size()==3){int first=*l.begin(),last=*(l.begin()+1),step=*(l.begin()+2);last=(last<0?last+size()+1:last);Rope<T>v;for(int i=first;i<last;i+=step)v.pub((*this)[i]);return v;}return *this;}Rope<T>operator+()const{return *this;}Rope<T>operator-()const{Rope<T>v;for(const T&e:*this)v.pub(-e);return v;}Rope<T>operator++(){for(int i=0;i<size();i++)replace(i,(*this)[i]+1);return *this;}Rope<T>operator--(){for(int i=0;i<size();i++)replace(i,(*this)[i]-1);return *this;}Rope<T>operator++(int32_t){Rope<T>v=*this;for(int i=0;i<size();i++)replace(i,(*this)[i]+1);return v;}Rope<T>operator--(int32_t){Rope<T>v=*this;for(int i=0;i<size();i++)replace(i,(*this)[i]-1);return v;}void out(){for(const T&e:*this)std::cout<<e<<'\n';}void outvec(){for(int i=0;i<size()-1;i++)std::cout<<(*this)[i]<<' ';std::cout<<last()<<'\n';}
T last()const{return (*this)[size()-1];}T sum(int l=0,int r=-1)const{T v=T();r=(r<0?r+size()+1:r);for(int i=l;i<r;i++)v+=(*this)[i];return v;}T prod(int l=0,int r=-1)const{T v=T()+1;r=(r<0?r+size()+1:r);for(int i=l;i<r;i++)v*=(*this)[i];return v;}T xorsum(int l=0,int r=-1)const{T v=T();r=(r<0?r+size()+1:r);for(int i=l;i<r;i++)v^=(*this)[i];return v;}T cumsumpart(int l,int r)const{return(*this)[r-1]-(l=0?0:(*this)[l-1]);}T cumxorpart(int l,int r)const{return(*this)[r-1]^(l=0?0:(*this)[l-1]);}int findgeq(const T&v){if(size()==0)return 0;if((*this)[0]<=last())return std::lower_bound(begin(),end(),v)-begin();else return size()-(std::lower_bound(rbegin(),rend(),v)-rbegin())-1;}int findleq(const T&v){if(size()==0)return 0;if((*this)[0]<=last())return std::upper_bound(begin(),end(),v)-begin()-1;else return size()-(std::upper_bound(rbegin(),rend(),v)-rbegin());}int countleq(const T&v){if(size()==0)return 0;if((*this)[0]<=last())return std::upper_bound(begin(),end(),v)-begin();else return std::upper_bound(rbegin(),rend(),v)-rbegin();}int countgeq(const T&v){if(size()==0)return 0;if((*this)[0]<=last())return size()-(std::lower_bound(begin(),end(),v)-begin());else return size()-(std::lower_bound(rbegin(),rend(),v)-rbegin());}int counteq(const T&v){return abs(findleq(v)-findgeq(v))+1;}};

// String class
class String:public std::string{typedef std::string SS;public:using SS::operator[];using SS::operator=;using SS::begin;using SS::end;using SS::rbegin;using SS::rend;using SS::resize;using SS::assign;using SS::push_back;using SS::pop_back;using SS::operator+=;String(){}String(const char*s):SS(s){}String(char c):SS(1,c){}String(int i,char c):SS(i,c){}String(int32_t i):SS(std::to_string(i)){}String(int64_t i):SS(std::to_string(i)){}String(const std::vector<char>&v){for(char e:v)pub(e);}String(const __gnu_pbds::tree<char,__gnu_pbds::null_type,std::less<char>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>&t){for(char e:t)pub(e);}String(const __gnu_cxx::rope<char>&r){for(char e:r)pub(e);}void pub(char c){push_back(c);}void pub(String s){for(char c:s)push_back(c);}void pob(){SS::pop_back();}
String operator[](const std::initializer_list<int>&l)const{if(l.size()==2||l.size()==3){int first=*l.begin(),last=*(l.begin()+1),step=(l.size()==2?1:*(l.begin()+2));last=(last<0?last+size()+1:last);String s;for(int i=first;i<last;i+=step)s.pub((*this)[i]);return s;}return *this;}String operator+(const String&s)const{String r(*this);r.pub(s);return r;}char last()const{return(*this)[size()-1];}String&operator<<(const String&s){pub(s);return *this;}char&last(){return(*this)[size()-1];}int size()const{return SS::size();}int32_t toInt()const{return std::stoi(*this);}int64_t toLong()const{return std::stol(*this);}std::vector<int>find(const String&s)const{Vector<int>v;int i=SS::find(s);while(i!=SS::npos){v.pub(i);i=SS::find(s,i+s.size());}return v;}std::vector<int>find_dup(const String&s)const{Vector<int>v;int i=SS::find(s);while(i!=SS::npos){v.pub(i);i=SS::find(s,i+1);}return v;}
void reverse(){std::reverse(begin(),end());}void insert(int i,const String&s){SS::insert(i,s);}void erase(int i){SS::erase(i,1);}void erase(int i,int j){SS::erase(i,j-i);}void erase_unique(){SS::erase(std::unique(begin(),end()),end());}void rotatedown(int i){std::rotate(begin(),begin()+i,end());}void rotateup(int i){std::rotate(rbegin(),rbegin()+i,rend());}void sortup(){int m=*std::min_element(begin(),end());int M=*std::max_element(begin(),end());std::vector<char>b(M-m+1);for(char e:*this)b[e-m]++;for(int i=0;i<b.size()-1;i++)b[i+1]+=b[i];for(int i=0;i<b.size();i++)for(int j=(i==0?0:b[i-1]);j<b[i];j++)(*this)[j]=m+i;}void sortdown(){sortup();reverse();}
String reversed()const{String r(*this);r.reverse();return r;}String inserted(int i,const String&s)const{String r(*this);r.insert(i,s);return r;}String erased(int i)const{String r(*this);r.erase(i);return r;}String erased(int i,int j)const{String r(*this);r.erase(i,j);return r;}String erase_uniqued()const{String r(*this);r.erase_unique();return r;}String rotatedowned(int i)const{String r(*this);r.rotatedown(i);return r;}String rotateuped(int i)const{String r(*this);r.rotateup(i);return r;}String sortuped()const{String r(*this);r.sortup();return r;}String sortdowned()const{String r(*this);r.sortdown();return r;}};

// Trie class
class Trie:public __gnu_pbds::trie<std::string,__gnu_pbds::null_type,__gnu_pbds::trie_string_access_traits<>,__gnu_pbds::pat_trie_tag,__gnu_pbds::trie_prefix_search_node_update>{public:typedef __gnu_pbds::trie<std::string,__gnu_pbds::null_type,__gnu_pbds::trie_string_access_traits<>,__gnu_pbds::pat_trie_tag,__gnu_pbds::trie_prefix_search_node_update>tree;using tree::operator=;using tree::begin;using tree::end;using tree::insert;using tree::erase;using tree::split;Trie(const tree&t):tree(t){}Trie(int n=0){for(int i=0;i<-n;i++){std::string v;std::cin>>v;insert(v);}}Trie(const std::initializer_list<std::string>&l){for(const std::string&e:l)insert(e);}int size()const{return tree::size();}bool contains(const std::string&s)const{return tree::find(s)!=end();}void merge(const tree&s){tree t=s;tree::join(t);}std::pair<Trie,Trie>splitted(const std::string&s)const{Trie r=*this,t;r.split(s,t);return std::make_pair(r,t);}
void eraseall(const std::string&s){std::vector<std::string>match=(*this)[s];for(const std::string&e:match)erase(e);}void exploit(const std::string&s){std::vector<std::string>match;std::pair<tree::const_iterator,tree::const_iterator>range=prefix_range(s);for(tree::const_iterator it=begin();it!=range.first;++it)match.push_back(*it);for(tree::const_iterator it=range.second;it!=end();++it)match.push_back(*it);for(const std::string&e:match)erase(e);}Trie&operator<<(const std::string&s){insert(s);return *this;}Trie&operator<<(const tree&t){merge(t);return *this;}Trie&operator>>(const std::string&s){erase(s);return *this;}bool operator>(const std::string&s){return contains(s);}std::vector<std::string>operator[](const std::string&s)const{std::vector<std::string>match;std::pair<tree::const_iterator,tree::const_iterator>range=prefix_range(s);for(tree::const_iterator it=range.first;it!=range.second;++it)match.push_back(*it);return match;}};std::ostream&operator<<(std::ostream&o,const Trie&t){auto it=t.begin();for(int i=0;i<t.size()-1;i++,it++)o<<*it<<'\n';return o<<*it;}

// Modulo class
#define ModCalc(OP) Modulo operator OP(const Modulo&l,const Modulo&r){return Modulo(l.val()OP r.val());}Modulo operator OP(const Modulo&l,const int64_t&r){return Modulo(l.val()OP Modulo(r));}Modulo operator OP(const int64_t&l,const Modulo&r){return Modulo(l)OP r.val();}Modulo operator OP##=(Modulo&l,const Modulo&r){return l=l OP r;}Modulo operator OP##=(Modulo&l,const int64_t&r){return l=l OP r;}int64_t operator OP##=(int64_t&l,const Modulo&r){return l=l OP r.val();}
#define ModComp(OP) bool operator OP(const Modulo&l,const Modulo&r){return l.val()OP r.val();}bool operator OP(const Modulo&l,const int64_t&r){return l.val()OP r;}bool operator OP(const int64_t&l,const Modulo&r){return l OP r.val();}
class Modulo{int64_t value;public:Modulo():value(0){}Modulo(const int64_t&v){value=v;normalize();}void normalize(){value=(value%mod()+mod())%mod();}Modulo(const Modulo&m):value(m.val()){}Modulo inv()const{int64_t a=value;int64_t b=mod(),u=0,v=1;while(a>1){u-=b/a*v;b%=a;std::swap(a,b);std::swap(u,v);}return Modulo(v);}int64_t val()const{return value;}int64_t&val(){return value;}Modulo&operator=(const Modulo&m){value=m.val();return *this;}int64_t mod()const{return MOD;}Modulo&operator=(const int64_t&v){value=v;return *this;}Modulo operator++(){return Modulo(++value);}Modulo operator--(){return Modulo(--value);}Modulo operator++(int32_t){return Modulo(value++);}Modulo operator--(int32_t){return Modulo(value--);}Modulo operator+()const{return *this;}Modulo operator-()const{return Modulo(-value);}Modulo power(int64_t i)const{int64_t x=value;int64_t r=1;while(i>0){if(i&1)r=r*x%mod();x=x*x%mod();i/=2;}return Modulo(r);}};std::ostream&operator<<(std::ostream&o,const Modulo&m){return o<<m.val();}std::istream&operator>>(std::istream&i,Modulo&m){i>>m.val();m.normalize();return i;}ModCalc(+)ModCalc(-)ModCalc(*)ModCalc(<<)ModCalc(>>)ModCalc(&)ModCalc(|)ModCalc(^)ModComp(==)ModComp(!=)ModComp(>=)ModComp(<=)ModComp(>)ModComp(<)Modulo operator/(const Modulo&l,const Modulo&r){return Modulo(l.val()*r.inv());}Modulo operator/(const Modulo&l,const int64_t&r){return Modulo(l.val()*Modulo(r).inv());}Modulo operator/(const int64_t&l,const Modulo&r){return Modulo(Modulo(l)*r.inv());}

// Matrix class need Vector class
#define MatCalc(OP) Matrix<T>operator OP(const VVT&r)const{Matrix<T>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=(*this)[i]OP r[i];v.rect();return v;}Matrix<T>operator OP(const VT&r)const{Matrix<T>v(std::min(size(),r.size()));for(int i=0;i<size();i++)v[i]=(*this)[i]OP r;return v;}Matrix<T>operator OP(const T&r)const{Matrix<T>v(size());for(int i=0;i<size();i++)v[i]=(*this)[i]OP r;return v;}Matrix<T>operator OP##=(const VVT&r){return *this=*this OP r;}Matrix<T>operator OP##=(const VT&r){return *this=*this OP r;}Matrix<T>operator OP##=(const T&r){return *this=*this OP r;}
#define MatComp(OP) Matrix<int>operator OP(const VVT&r)const{Matrix<int>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=(*this)[i]OP r[i];r.rect();return v;}Matrix<int>operator OP(const VT&r)const{Matrix<int>v(size());for(int i=0;i<size();i++)v[i]=(*this)[i]OP r;return v;}Matrix<int>operator OP(const T&r)const{Matrix<int>v(size());for(int i=0;i<size();i++)v[i]=(*this)[i]OP r;return v;}
template<typename T>class Matrix:private Vector<Vector<T>>{typedef Vector<T>VT;typedef Vector<VT>VVT;using VVT::insert;using VVT::erase;using VVT::pob;using VVT::pub;public:using VVT::operator+;using VVT::operator-;using VVT::operator++;using VVT::operator--;using VVT::operator[];using VVT::begin;using VVT::end;using VVT::rbegin;using VVT::rend;using VVT::resize;using VVT::assign;using VVT::size;using VVT::out;using VVT::last;
Matrix(){}Matrix(const VVT&m):VVT(m){rect();}Matrix(const VT&v):VVT(1,v){}Matrix(int c,int r=0,T v=T()){if(c>=0&&r>=0)assign(c,r,v);else{assign(-c,-r,v);for(VT&e:*this)std::cin>>e;}}Matrix(std::pair<int,int>p,T v=T()){assign(p.first,p.second,v);}Matrix(const std::initializer_list<std::initializer_list<T>>&l){resize(l.size());for(int i=0;i<size();i++)(*this)[i]=*(l.begin()+i);rect();}template<typename U>Matrix(const Matrix<U>&v){resize(v.size());for(int i=0;i<size();i++)(*this)[i]=v[i];}void rect(){VT v(size());for(int i=0;i<size();i++)v[i]=(*this)[i].size();resize(size(),v.max());}std::pair<int,int>shape()const{return std::make_pair(size(),size()==0?0:(*this)[0].size());}bool isEmpty(){return shape().first==0&&shape().second==0;}void resize(int c,int r,T v=T()){resize(c);for(VT&e:*this)e.resize(r,v);}void resize(std::pair<int,int>p,T v=T()){resize(p.first,p.second,v);}void assign(int c,int r,T v){assign(c,VT(r,v));}void assign(std::pair<int,int>p,const T&v){assign(p.first,p.second,v);}T operator[](std::pair<int,int>p)const{return(*this)[p.first][p.second];}T&operator[](std::pair<int,int>p){return(*this)[p.first][p.second];}
Matrix<T>operator[](const std::pair<std::initializer_list<T>,std::initializer_list<T>>&p)const{int columnFirst=*p.first.begin(),columnLast=*(p.first.begin()+1),columnStep=(p.first.size()==2?1:*(p.first.begin()+2));columnLast=(columnLast<0?columnLast+size()+1:columnLast);int rowFirst=*p.second.begin(),rowLast=*(p.second.begin()+1),rowStep=(p.second.size()==2?1:*(p.second.begin()+2));rowLast=(rowLast<0?rowLast+size()+1:rowLast);Matrix<T>m;for(int i=columnFirst;i<columnLast;i+=columnStep){VT v;for(int j=rowFirst;j<rowLast;j+=rowStep)v.pub((*this)[i][j]);m.vstack(v);}return m;}VT vector()const{VT v;for(const VT&e:*this)v.pub(e);return v;}T sum(int cl=0,int rl=0,int cr=-1,int rr=-1)const{T v=T();cr=(cr<0?cr+size()+1:cr);for(int i=cl;i<cr;i++)v+=(*this)[i].sum(rl,rr);return v;}T prod(int cl=0,int rl=0,int cr=-1,int rr=-1)const{T v=T()+1;cr=(cr<0?cr+size()+1:cr);for(int i=cl;i<cr;i++)v*=(*this)[i].prod(rl,rr);return v;}T xorsum(int cl=0,int rl=0,int cr=-1,int rr=-1)const{T v=T();cr=(cr<0?cr+size()+1:cr);for(int i=cl;i<cr;i++)v^=(*this)[i].xorsum(rl,rr);return v;}Matrix<T>&operator=(const VVT&v){resize(v.size());for(int i=0;i<size();i++)(*this)[i]=v[i];rect();}Matrix<T>&operator=(const VT&v){assign(1,v);return *this;}
std::pair<int,int>argmin()const{VT v(size());for(int i=0;i<size();i++)v[i]=(*this)[i].min();int m=v.argmin();return std::make_pair(m,(*this)[m].argmin());}std::pair<int,int>argmax()const{VT v(size());for(int i=0;i<size();i++)v[i]=(*this)[i].max();int m=v.argmax();return std::make_pair(m,(*this)[m].argmax());}T min()const{VT v(size());for(int i=0;i<size();i++)v[i]=(*this)[i].min();return v.min();}T max()const{VT v(size());for(int i=0;i<size();i++)v[i]=(*this)[i].max();return v.max();}void dot(Matrix<T>v){Matrix<T>m(*this);assign(shape().first,v.shape().second,0);for(int i=0;i<shape().first;i++)for(int j=0;j<shape().second;j++)for(int k=0;k<std::min(m.shape().second,v.shape().first);k++)(*this)[i][j]+=m[i][k]*v[k][j];}void vstack(const VT&v){if(shape().second<v.size()&&size()>0){pub(v[{0,shape().second}]);}else{pub(v);last().resize(shape().second);}}void vstack(const VVT&v){for(const VT&e:v)vstack(e);}void hstack(const VT&v){if(size()==0)resize(v.size());for(int i=0;i<std::min(size(),v.size());i++)(*this)[i].pub(v[i]);resize(shape());}void hstack(const VVT&v){if(size()==0)resize(v.size());for(int i=0;i<std::min(size(),v.size());i++)(*this)[i].pub(v[i]);rect();}void vpob(){pob();}void hpob(){for(VT&e:*this)e.pob();}
void verase(int i){erase(i);}void verase(int i,int j){erase(i,j);}void herase(int i){for(VT&e:*this)e.erase(i);}void herase(int i,int j){for(VT&e:*this)e.erase(i,j);}void vinsert(int i,const VT&v){if(isEmpty())(*this)=v;else{insert(i,v[{0,std::min(shape().second,v.size()),1}]);if(i==0)rect();else(*this)[i].resize(shape().second);}}void vinsert(int i,const Matrix<T>&v){if(isEmpty())(*this)=v;else{insert(i,v[{{0,-1,1},{0,std::min(shape().second,v.shape().second),1}}]);if(i==0)rect();else(*this)[i].resize(shape().second);}}void hinsert(int i,const VT&v){if(isEmpty())(*this)=v;else for(int j=0;j<std::min(size(),v.size());j++)(*this)[j].insert(i,v[j]);for(int j=std::min(size(),v.size());j<size();j++)(*this)[j].insert(i,0);}void hinsert(int i,const Matrix<T>&v){if(isEmpty())(*this)=v;else for(int j=0;j<std::min(size(),v.size());j++)(*this)[j].insert(i,v[j]);for(int j=std::min(size(),v.size());j<size();j++)(*this)[j].resize(v.shape().second);}void transpose(){std::pair<int,int>s=shape();if(s.first<s.second)for(int i=0;i<s.second-s.first;i++)pub(VT(s.first));else for(int i=0;i<s.second;i++)(*this)[i].resize(s.first);for(int i=0;i<std::min(s.first,s.second);i++)for(int j=i+1;j<size();j++)std::swap((*this)[i][j],(*this)[j][i]);resize(s.second,s.first);}
void power(int n){Matrix<T>m(*this);assign(size(),size(),0);for(int i=0;i<size();i++)(*this)[i][i]=1;while(n>0){if(n&1)dot(m);m.dot(m);n/=2;}}void cumsum(){VVT::cumsum();for(VT&e:*this)e.cumsum();}void decumsum(){VVT::decumsum();for(VT&e:*this)e.decumsum();}T cumsumpart(int cl,int rl,int cr,int rr)const{return(*this)[cr-1][rr-1]-(cl==0?0:(*this)[cl-1][rr-1])-(rl==0?0:(*this)[cr-1][rl-1])+((cl==0||rl==0)?0:(*this)[cl-1][rl-1]);}void cumxor(){VVT::cumxor();for(VT&e:*this)e.cumxor();}void decumxor(){VVT::decumxor();for(VT&e:*this)e.decumxor();}T cumxorpart(int cl,int rl,int cr,int rr)const{return (*this)[cr-1][rr-1]^(cl==0?0:(*this)[cl-1][rr-1])^(rl==0?0:(*this)[cr-1][rl-1])^((cl==0||rl==0)?0:(*this)[cl-1][rl-1]);}void compress(){VT u=vector();u.sortup();u.erase_unique();std::unordered_map<T,int>m;for(int i=0;i<u.size();i++)m[u[i]]=i;for(int i=0;i<shape().first;i++)for(int j=0;j<shape().second;j++)(*this)[i][j]=m[(*this)[i][j]];}MatCalc(+)MatCalc(-)MatCalc(*)MatCalc(/)MatCalc(%)MatCalc(<<)MatCalc(>>)MatCalc(&)MatCalc(|)MatCalc(^)MatComp(==)MatComp(!=)MatComp(>=)MatComp(<=)MatComp(>)MatComp(<)
Matrix<T>vstacked(const VT&v)const{Matrix<T>r(*this);r.vstack(v);return r;}Matrix<T>vstacked(const VVT&v)const{Matrix<T>r(*this);r.vstack(v);return r;}Matrix<T>hstacked(const VT&v)const{Matrix<T>r(*this);r.hstack(v);return r;}Matrix<T>hstacked(const VVT&v)const{Matrix<T>r(*this);r.hstack(v);return r;}Matrix<T>vpobed()const{Matrix<T>r(*this);r.vpob();return r;}Matrix<T>hpobed()const{Matrix<T>r(*this);r.hpob();return r;}Matrix<T>verased(int i)const{Matrix<T>r(*this);r.verase(i);return r;}Matrix<T>verased(int i,int j)const{Matrix<T>r(*this);r.verase(i,j);return r;}Matrix<T>herased(int i)const{Matrix<T>r(*this);r.herase(i);return r;}Matrix<T>herased(int i,int j)const{Matrix<T>r(*this);r.herase(i,j);return r;}Matrix<T>vinserted(int i,const VT&v)const{Matrix<T>r(*this);r.vinsert(i,v);return r;}Matrix<T>vinserted(int i,const Matrix<T>&v)const{Matrix<T>r(*this);r.vinsert(i,v);return r;}Matrix<T>hinserted(int i,const VT&v)const{Matrix<T>r(*this);r.hinsert(i,v);return r;}Matrix<T>hinserted(int i,const Matrix<T>&v)const{Matrix<T>r(*this);r.hinsert(i,v);return r;}Matrix<T>transposed()const{Matrix<T>r(*this);r.transpose();return r;}Matrix<T>powered(int n)const{Matrix<T>r(*this);r.power(n);return r;}Matrix<T>cumsumed()const{Matrix<T>r(*this);r.cumsum();return r;}Matrix<T>decumsumed()const{Matrix<T>r(*this);r.decumsum();return r;}Matrix<T>cumxored()const{Matrix<T>r(*this);r.cumxor();return r;}Matrix<T>decumxored()const{Matrix<T>r(*this);r.decumxor();return r;}Matrix<T>compressed()const{Matrix<T>r(*this);r.compress();return r;}};

// FFT, NNT need Vector Modulo class
std::unordered_map<int,int>MOD_ROOT={{1224736769,3},{1053818881,7},{1051721729,6},{1045430273,3},{1012924417,5},{1007681537,3},{1004535809,3},{998244353,3},{985661441,3},{976224257,3},{975175681,17},{962592769,7},{950009857,7},{943718401,7},{935329793,3},{924844033,5},{469762049,3},{167772161,3}};Vector<std::complex<double>>fft(Vector<std::complex<double>>a,bool inverse=false){int n=a.size(),h=std::log2(n);for(int i=0;i<n;i++){int j=0;for(int k=0;k<h;k++)j|=(i>>k&1)<<(h-1-k);if(i<j)std::swap(a[i],a[j]);}for(int b=1;b<n;b*=2){for(int j=0;j<b;j++){std::complex<double>w=std::polar(1.0,(2*M_PI)/(2*b)*j*(inverse?1:-1));for(int k=0;k<n;k+=b*2){std::complex<double>s=a[j+k],t=a[j+k+b]*w;a[j+k]=s+t;a[j+k+b]=s-t;}}}a/=std::complex<double>(inverse?n:1);return a;}Vector<Modulo>ntt(Vector<Modulo>a,bool inverse=false){int n=a.size(),h=std::log2(n);Modulo root=MOD_ROOT[MOD];for(int i=0;i<n;i++){int j=0;for(int k=0;k<h;k++)j|=(i>>k&1)<<(h-1-k);if(i<j)std::swap(a[i],a[j]);}for(int b=1;b<n;b*=2){Modulo w=root.power((a[0].mod()-1)/(b*2));if(inverse)w=w.inv();for(int j=0;j<n;j+=b*2){Modulo wn=1;for(int k=0;k<b;k++){Modulo s=a[j+k+0],t=a[j+k+b]*wn;a[j+k]=s+t;a[j+k+b]=s-t;wn=wn*w;}}}if(inverse){Modulo v=Modulo(n).inv();a*=v;}return a;}
Vector<double>convolve(Vector<double>a,Vector<double>b){if(a.size()==0||b.size()==0)return Vector<double>();int s=a.size()+b.size()-1,t=std::pow(2,std::ceil(std::log2(s)));a.resize(t);b.resize(t);Vector<std::complex<double>>A=fft(a),B=fft(b);A*=B;A=fft(A,true);a.resize(s);for(int i=0;i<s;i++)a[i]=A[i].real();return a;}Vector<int>convolve(Vector<int>a,Vector<int>b){return convolve(Vector<double>(a),Vector<double>(b))+0.5;}Vector<Modulo>convolve(Vector<Modulo>a,Vector<Modulo>b){if(a.size()==0||b.size()==0)return Vector<Modulo>();int s=a.size()+b.size()-1,t=std::pow(2,std::ceil(std::log2(s)));a.resize(t);b.resize(t);Vector<Modulo>A=ntt(a),B=ntt(b);A*=B;a=ntt(A,true);a.resize(s);return a;}

// MultipleVector class need Vector, Modulo class
class MultipleVector{Vector<Modulo>vfact,ifact,pows;Modulo p;public:MultipleVector(int n=0,int _p=1):vfact(Vector<Modulo>(1,1)),ifact(Vector<Modulo>(1,1)),pows(Vector<Modulo>(1,1)),p(_p){resize(n);}void resize(int n){if(vfact.size()>=n)return;int s=vfact.size();vfact.resize(n+1);for(int i=s;i<=n;i++)vfact[i]=i*vfact[i-1];ifact.resize(n+1);ifact[n]=vfact[n].inv();for(int i=n;i>s;i--)ifact[i-1]=i*ifact[i];pows.resize(n+1);for(int i=s;i<=n;i++)pows[i]=p*pows[i-1];}Modulo fact(Modulo n){resize(n.val());return vfact[n.val()];}Vector<Modulo>facts(Modulo n){resize(n.val());return vfact[{0,n.val(),1}];}Modulo factinv(Modulo n){resize(n.val());return ifact[n.val()];}Vector<Modulo>factinvs(Modulo n){resize(n.val());return ifact[{0,n.val(),1}];}Modulo power(Modulo n){resize(n.val());return pows[n.val()];}Vector<Modulo>powers(Modulo n){resize(n.val());return pows[{0,n.val(),1}];}Modulo parm(Modulo n,Modulo r){if(n<r)return Modulo();resize(n.val());return vfact[n.val()]*ifact[(n-r).val()];}Modulo comb(Modulo n,Modulo r){if(n<r)return Modulo();resize(n.val());return vfact[n.val()]*ifact[(n-r).val()]*ifact[r.val()];}Modulo homo(Modulo n,Modulo r){return comb(n+r-1,r);}};

// Eratos class need Vector class
class Eratos{Vector<int>divs,prms,ords;int order_max;public:Eratos(int n=0):order_max(0){resize(n);}int size()const{return divs.size();}void resize(int n){if(size()>=n)return;int m=size();divs.resize(n+1);for(int i=m;i<2;i++)if(i<size())divs[i]=-1;int r=std::sqrt(n-1)+1;for(int i=2;i<r;i++)if(divs[i]==0)for(int j=std::max((m-1)/i+1,(int)2)*i;j<=n;j+=i)divs[j]=(divs[j]==0?i:divs[j]);for(int i=m;i<=n;i++)if(divs[i]==0)prms.pub(i);ords.resize(n+1);for(int i=m;i<=n;i++)ords[i]=(divs[i]==0?++order_max:0);}Vector<int>divisors()const{return divs;}Vector<int>primes()const{return prms;}Vector<int>orders()const{return ords;}};

// Unionfind class need Vector class
template<typename T>class Unionfind{Vector<int>p;Vector<T>w;int sign(int x){return(x>0)-(x<0);}int get(int x){if(p[x]==(x+1))return x+1;else{int parent=sign(p[x])*get(abs(p[x])-1);w[x]+=w[abs(p[x])-1];return p[x]=parent;}}void get(int&x,int&y){x=get(x);y=get(y);}int weight(int x){get(x);return w[x];}public:Unionfind(int n=0){resize(n);}void resize(const int&n){p.resize(n);for(int i=w.size();i<p.size();i++)p[i]=i+1;w.resize(n);}int size()const{return p.size();}bool unite(int x,int y,T vv=T()){if(vv<0){std::swap(x,y);vv*=-1;}vv+=weight(x)-weight(y);get(x,y);if(abs(x)==abs(y))return vv==weight(x)-weight(y);p[abs(y)-1]=x*sign(y);w[abs(y)-1]=vv;return true;}bool separate(int x,int y,T vv=T()){if(vv<0){std::swap(x,y);vv*=-1;}vv+=weight(x)-weight(y);get(x,y);if(abs(x)==abs(y))return vv==weight(x)-weight(y);p[abs(y)-1]=-x*sign(y);w[abs(y)-1]=vv;return true;}int same(int x,int y){get(x,y);return (x==y)-(x==-y);}Vector<int>same(int x){Vector<int>v(size());for(int i=0;i<size();i++)v[i]=same(x,i);return v;}T diff(int x,int y){return sign(same(x,y))*(weight(y)-weight(x));}Vector<T>diff(int x){Vector<int>v(size());for(int i=0;i<size();i++)v[i]=diff(x,i);return v;}};

// Graph class need Vector class
template<typename T>struct Edge{int from,to;T cost;Edge(int f=0,int t=0,T c=T()):from(f),to(t),cost(c){}};template<typename T>std::istream&operator>>(std::istream&i,Edge<T>&e){i>>e.from>>e.to>>e.cost;return i;}template<typename T>std::ostream&operator<<(std::ostream&o,const Edge<T>&e){return o<<e.from<<' '<<e.to<<' '<<e.cost;}template<typename T>class Graph{public:Vector<Edge<T>>edge;Vector<Vector<int>>node;Graph(int n=0){resize(n);}void resize(int n){node.resize(n);}void clear(){edge=Vector<Edge<T>>();node=Vector<Vector<int>>(nodes());}int edges()const{return edge.size();}int nodes()const{return node.size();}virtual int add(int from,int to,T cost)=0;Vector<T>dijkstra(int start){Vector<T>d(nodes(),std::numeric_limits<T>::max());std::priority_queue<std::pair<T,int>,std::vector<std::pair<T,int>>,std::greater<std::pair<T,int>>>s;d[start]=0;s.emplace(d[start],start);while(!s.empty()){T dist=s.top().first;int from=s.top().second;s.pop();if(d[from]<dist)continue;for(int id:node[from]){int to=edge[id].from^edge[id].to^from;if(d[from]+edge[id].cost<d[to]){d[to]=d[from]+edge[id].cost;s.emplace(d[to],to);}}}return d;}};
// Undigraph class need Vector, Graph class
template<typename T>class Undigraph:public Graph<T>{Vector<int>brgs,crus,lows,ords;bool lowlinked;int lowlink_dfs(int from,int k,int parent){ords[from]=lows[from]=k++;bool is_crunode=false;int cnt=0;for(int id:node[from]){int to=edge[id].from^edge[id].to^from;if(ords[to]==-1){cnt++;k=lowlink_dfs(to,k,from);lows[from]=std::min(lows[from],lows[to]);is_crunode|=parent!=-1&&lows[to]>=ords[from];if(ords[from]<lows[to])brgs.pub(id);}else if(to!=parent)lows[from]=std::min(lows[from],lows[to]);}is_crunode|=parent==-1&&cnt>1;if(is_crunode)crus.pub(from);return k;}void lowlink(){brgs=Vector<int>();crus=Vector<int>();ords.assign(this->nodes(),-1),lows.assign(this->nodes(),-1);int k=0;for(int i=0;i<this->nodes();i++)if(ords[i]==-1)k=lowlink_dfs(i,k,-1);lowlinked=true;}public:using Graph<T>::edge;using Graph<T>::node;Undigraph(int n=0):Graph<T>(n){lowlinked=false;}int add(int from,int to,T cost=1){int id=this->edges();node[from].pub(id);node[to].pub(id);edge.pub(Edge<T>(from,to,cost));return id;}void reset_lowlink(){lowlink();}Vector<int>bridges(){if(!lowlinked)lowlink();return brgs;}Vector<int>crunodes(){if(!lowlinked)lowlink();return crus;}
T prim(int start=0){Vector<std::pair<T,std::pair<int,int>>>cft;T total = 0;Vector<int>used(this->nodes(),0);std::priority_queue<std::pair<T,std::pair<int,int>>,std::vector<std::pair<T,std::pair<int,int>>>,std::greater<std::pair<T,std::pair<int,int>>>>s;s.emplace(std::make_pair(0,std::make_pair(-1,start)));while(!s.empty()){T cost=s.top().first;int fromfrom=s.top().second.first,from=s.top().second.second;s.pop();if(used[from])continue;used[from]=true;total+=cost;if(fromfrom>-1)cft.pub(std::make_pair(cost,std::make_pair(fromfrom,from)));for(int id:node[from]){int to=edge[id].from^edge[id].to^from;s.emplace(std::make_pair(edge[id].cost,std::make_pair(from,to)));}}this->clear();for(std::pair<T,std::pair<int,int>>e:cft)add(e.second.first,e.second.second,e.first);return total;}};
// Forest class need Vector, Graph, Undigraph class
template<typename T>class Forest:public Undigraph<T>{
bool table_created;Vector<Vector<int>>lca_table;void root_dfs(int from){for(int&id:node[from]){if(from==edge[id].from)std::swap(edge[id].from,edge[id].to);int to=edge[id].from;if(root[to]!=-1)continue;root[to]=root[from];parent[to]=from;depth[to]=depth[from]+1;dist[to]=dist[from]+edge[id].cost;children[from].pub(to);root_dfs(to);treesize[from]+=treesize[to];}}void make_lca_table(){Vector<int>next_parent=parent;while((next_parent==Vector<int>(this->nodes(),-1)).sum()<this->nodes()){lca_table.pub(next_parent);for(int i=0;i<this->nodes();i++){next_parent[i]=(next_parent[i]==-1?-1:lca_table.last()[next_parent[i]]);}}table_created=true;}public:Vector<int>root,parent,treesize,depth;Vector<T>dist;Vector<Vector<int>>children;using Undigraph<T>::edge;using Undigraph<T>::node;using Undigraph<T>::resize;using Undigraph<T>::edges;using Undigraph<T>::nodes;
Forest(int n=0):Undigraph<T>(n){initialize();table_created=false;}void initialize(){root.assign(nodes(),-1);parent.assign(nodes(),-1);treesize.assign(nodes(),1);depth.assign(nodes(),0);dist.assign(nodes(),0);children.assign(nodes(),Vector<int>());}void setTreeRoot(int n){initialize();root[n]=n;root_dfs(n);}void setForestRoot(){initialize();for(int n=0;n<nodes();n++)if(root[n]==-1){root[n]=n;root_dfs(n);};}T diameter(int n=0){setTreeRoot(n);int terminal=dist.argmax();setTreeRoot(terminal);return dist.max();}int ancestor(int n,int i){if(!table_created)make_lca_table();if(i<0)return -1;i=depth[n]-i;for(int j=0;i>0;j++){if(i&1)n=lca_table[j][n];i/=2;}return n;}int lca(int u,int v){if(depth[u]>depth[v])std::swap(u,v);int i=0,j=depth[u];while(j-i>1){int m=(i+j)/2;if(ancestor(u,m)==ancestor(v,m))i=m;else j=m;}return ancestor(u,i);}void reset_lca(){lca_table=Vector<Vector<int>>();make_lca_table();}};
// Digraph class need Vector, Graph class
template<typename T>class Digraph:public Graph<T>{Vector<Vector<int>>rev_node;Vector<Edge<T>>rev_edge;Vector<int>strong_edgeid,weak_edgeid,strong_id,ords;bool scced;void scc_dfs(int from){if(strong_id[from]==-1)return;strong_id[from]=-1;for(int id:node[from]){int to=edge[id].from^edge[id].to^from;scc_dfs(to);}ords.pub(from);}void scc_rdfs(int from,int cnt){if(strong_id[from]!=-1)return;strong_id[from]=cnt;for(int id:rev_node[from]){int to=rev_edge[id].from^rev_edge[id].to^from;if(strong_id[to]==-1){strong_edgeid.pub(id);scc_rdfs(to,cnt);}else if(strong_id[to]==cnt)strong_edgeid.pub(id);else if(strong_id[to]<cnt)weak_edgeid.pub(id);}}public:using Graph<T>::edge;using Graph<T>::node;Digraph(int n=0):Graph<T>(n),scced(false){}int add(int from,int to,T cost=1){int id=this->edges();node[from].pub(id);edge.pub(Edge<T>(from,to,cost));return id;}Digraph<T>reversed()const{Digraph<T>r(this->edges());for(Edge<T>e:edge)r.add(e.to,e.from,e.cost);return r;}
void scc(){strong_edgeid=Vector<int>();weak_edgeid=Vector<int>();strong_id.assign(this->nodes(),0);ords=Vector<int>(this->nodes());rev_node=Vector<Vector<int>>(this->nodes());rev_edge=Vector<Edge<T>>(this->edges());for(int id=0;id<this->edges();id++){rev_node[edge[id].to].pub(id);rev_edge[id]=Edge<T>(edge[id].to,edge[id].from,edge[id].cost);}for(int from=0;from<this->nodes();from++)scc_dfs(from);ords.reverse();int cnt=0;for(int from:ords)if(strong_id[from]==-1){scc_rdfs(from,cnt);cnt++;}Vector<Edge<T>>strong_edge;for(int id:strong_edgeid)strong_edge.pub(edge[id]);this->clear();for(Edge<T>e:strong_edge)add(e.from,e.to,e.cost);scced=true;}Vector<int>weakid(){if(!scced)scc();return weak_edgeid;};Vector<int>stronggroup(){if(!scced)scc();return strong_id;}
Vector<T>bellman(int start){Vector<T>d(this->nodes(),std::numeric_limits<T>::max());d[start]=0;bool negloop=false;Vector<int>updating(1,start);for(int i=0;i<this->nodes()&&updating.size()>0;i++){Vector<int>toUpdate;for(int from:updating){for(int id:node[from]){int to=edge[id].from^edge[id].to^from;if(d[to]>d[from]+edge[id].cost){d[to]=d[from]+edge[id].cost;toUpdate.pub(to);if(i==this->nodes()-1)d[to]=std::numeric_limits<T>::min();negloop=true;}}}updating=toUpdate;}if(negloop){for(int i=0;i<this->nodes()&&updating.size()>0;i++){Vector<int>toUpdate;for(int from:updating){for(int id:node[from]){int to=edge[id].from^edge[id].to^from;if(d[to]!=std::numeric_limits<T>::min()){d[to]=std::numeric_limits<T>::min();toUpdate.pub(to);}}}updating=toUpdate;}}return d;}Vector<int>topsort(){Vector<int>to_node(this->nodes(),0);for(Edge<T>e:edge)to_node[e.to]++;Vector<int>sorted;for(int i=0;i<this->nodes();i++)if(to_node[i]==0)sorted.pub(i);for(int i=0;i<sorted.size();i++)for(int id:node[sorted[i]]){if(--to_node[edge[id].to]==0)sorted.pub(edge[id].to);}if(sorted.size()!=this->nodes())return Vector<int>();return sorted;}};

// math function for Vector, Matrix, Modulo class
template<typename T>T sign(const T&x){return(x>0)-(x<0);}template<typename T>T abs(const T&x){return x*sign(x);}template<typename T>T power(T x,int y){T r=x*0+1;while(y>0){if(y&1)r*=x;x*=x;y/=2;}return r;}bool is_power(int n,int m){return n==power(llround(std::pow(n,(double)+1/m)),m);}int _gcd(const int&a,const int&b){return b?_gcd(b,a%b):a;}int gcd(const int&a,const int&b){return _gcd(std::max(a,b),std::min(a,b));}int lcm(const int&a,const int&b){return a/gcd(a,b)*b;}bool is_prime(int n){int m=std::sqrt(n-1)+1;for(int i=2;i<m+1;i++)if(n%i==0)return false;return n>1;}
int fact(int n){int v=1;for(int i=1;i<n+1;i++)v*=i;return v;}Modulo fact(Modulo n){Modulo v=1;for(int i=1;i<n+1;i++)v*=i;return v;}int parm(int n,int r){int v=1;for(int i=n-r+1;i<n+1;i++)v*=i;return v;}Modulo parm(Modulo n,Modulo r){Modulo v=1;for(int i=n.val()-r.val()+1;i<n.val()+1;i++)v*=i;return v;}int comb(int n,int r){int v=1;r=std::min(r,n-r);for(int i=0;i<r;i++){v*=n-i;v/=i+1;}return v;}Modulo comb(Modulo n,Modulo r){Modulo p=1,q=1;r=std::min(r,n-r);for(int i=0;i<r;i++){p*=n-i;q*=i+1;}return p/q;}int homo(int m,int n){return comb(m+n-1,n);}Modulo homo(Modulo m,Modulo n){return comb(m+n-1,n);}
Map<int,int>factor(int n){Map<int,int>f;for(int i=2;i*i<=n;i++)while(n%i==0){f[i]++;n/=i;}if(n!=1)f[n]++;return f;}
double toRad(double d){return d/180*M_PI;}double toDeg(double r){return r/M_PI*180;}


// ex. function_find(fname,0,1024,'u',100,output)
#define function_find(FUNCTION_INT_TO_VALUE,INT_RANGE_MIN,INT_RANGE_MAX,CHAR_KIND,VALUE_TARGET,INT_AND_OUTPUT) {int left=INT_RANGE_MIN-1;int right=INT_RANGE_MAX+1;bool outleft=(CHAR_KIND=='d'||CHAR_KIND=='U');int getmin=(CHAR_KIND=='u'||CHAR_KIND=='d')?1:-1;while(right-left>1){int mid=left+(right-left)/2;bool OK=FUNCTION_INT_TO_VALUE(mid)*getmin>=VALUE_TARGET*getmin;if(outleft==OK)left=mid;else right=mid;}INT_AND_OUTPUT=outleft?left:right;}

// BinaryIndexedTree class need Vector class
#define BITCalc(OP) BinaryIndexedTree<T>operator OP##=(const T&v){if(range.first+1==range.second)for(int i=range.first;i<size();i|=(i+1))t1[i]OP##=v;else for(int i=range.first;i<size();i|=(i+1)){t1[i]OP##=-v*(range.first-1);t2[i]OP##=v;}for(int i=range.second;i<size();i|=(i+1)){t1[i]OP##=v*(range.second-1);t2[i]OP##=-v;}return *this;}
template<typename T>class BinaryIndexedTree{Vector<T>t1,t2;std::pair<int,int>range;public:T sum(int x){T v=T();for(int i=x;i>=0;i=(i&(i+1))-1){v+=t1[i]+t2[i]*x;}return v;}T sum(int l,int r){return sum(r-1)-sum(l-1);}T get(int x){return sum(x,x+1);}void resize(int n){t1.resize(n);t2.resize(n);}int size()const{return t1.size();}Vector<T>firstVector()const{return t1;}Vector<T>secondVector()const{return t2;}BinaryIndexedTree(int n=0):range(std::make_pair(0,0)){resize(n);}BinaryIndexedTree(const BinaryIndexedTree&bit):t1(bit.firstVector()),t2(bit.secondVector()),range(std::make_pair(0,-1)){resize(bit.size());}BinaryIndexedTree<T>&operator=(const BinaryIndexedTree<T>&bit){resize(bit.size());t1=bit.firstVector();t2=bit.secondVector();return *this;}T operator[](int i)const{return get(i);}BinaryIndexedTree<T>&operator[](std::initializer_list<int>l){if(l.size()==1){range.first=*l.begin();range.second=(*l.begin())+1;}if(l.size()==2){range.first=*l.begin();range.second=(*(l.begin()+1)<0?*(l.begin()+1)+size()+1:*(l.begin()+1));}return *this;}BITCalc(+)BITCalc(-)T sum(){return sum(range.first,range.second);}BinaryIndexedTree<T>operator=(const T&v){for(int i=range.first;i<range.second;i++){operator[]({i});operator+=(-get(i)+v);}return *this;}Vector<T>toVector(){Vector<T>v(size());for(int i=0;i<size();i++)v[i]=get(i);return v;}};


// BIT^2

// 10^5 -> NlogN, 3000 -> N^2, 200 -> N^3, 50 -> N^4, 20 -> 2^N 
WRITE_FUNCTION_UNDER_HERE





int32_t main(){INIT;
  in(int,n,a,b);

  if((a+b)%2==0){
    out((b-a)/2);
  } else {
    int c1=a-1;
    int c2=n-b;
    int d;
    if(c1<c2){
      d = a;
      a = 1;
      b -= d;
    }else{
      d += n-b+1;
      a += d;
      b = n;
    }
    out(d+(b-a)/2);
  }
  

  
}

Measured memory_bytes: 256