//dsu,modint,segtree,fenwick_tree,ntt,convolution,FPS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define REP(i,l,r) for(int i=l;i<(r);++i) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define el "\n" template// MOD is prime. struct modint { long long x; modint (long long v=0){ x=v%MOD; if(x<0)x+=MOD; } int val()const{ return x; } modint&operator+=(const modint&a){ x+=a.x; if(x>=MOD)x-=MOD; return *this; } modint&operator*=(const modint&a){ x=x*a.x%MOD; return *this; } modint&operator-=(const modint&a){ x-=a.x; if(x<0)x+=MOD; return *this; } modint operator+(const modint&a)const{ modint res=*this; return res+=a; } modint operator-(const modint &a)const{ modint res = *this; return res-=a; } modint operator*(const modint&a)const{ modint res=*this; return res*=a; } modint pow(long long n)const{ modint a=*this; modint res=1; while(n){ if(n&1)res*=a; a*=a; n>>=1; } return res; } modint inv() const{ return pow(MOD-2);//MOD is prime. } modint&operator/=(const modint&a){ return *this*=a.inv(); } modint operator/(const modint&a)const{ modint res = *this; return res/=a; } modint operator-() const{ return modint(-x); } bool operator==(const modint&a)const{ return x==a.x; } bool operator!=(const modint&a)const{ return x!=a.x; } }; using mint = modint<998244353>; //////////// //NTT void ntt(vector&a,bool inverse){ int n = a.size(); for(int i=1,j=0;i>1; while(j&bit){ j^=bit; bit>>=1; } j^=bit; if(i convolution(vectora,vector b){ if(a.empty()||b.empty()){ return {}; } int need=a.size()+b.size()-1; int n=1; while(n; struct FPS:vm{ #define d (*this) #define s int(size()) using vm::vector; FPS(initializer_lista):vm(a){} FPS low(int n)const{ FPS r=d;r.resize(n);return r; } mint&operator[](int i){ if(i>=s)resize(i+1); return vm::operator[](i); } mint operator[](int i)const{ return ilow(sz); q[0]+=1; g=(g*q).low(sz); } return g.low(n); } FPS pow(long long k,int n)const{ if(n==0)return {}; if(k==0){ FPS res(n); res[0]=1; return res; } int v=0; while(v(n-1)/k)return FPS(n); int shift=v*k; int need=n-shift; mint c=d[v]; FPS h; h.resize(s-v); for(int i=v;i p,sz; int group_count; dsu(int n):p(n),sz(n,1),group_count(n){ iota(p.begin(),p.end(),0); } int leader(int x){ if(p[x]==x)return x; return p[x]=leader(p[x]); } bool merge(int a,int b){ a=leader(a); b=leader(b); if(a==b)return false; if(sz[a] 90 degree clockwise rotation(In-place) void rotate90(vector&S){ int N = S.size(); for(int i=0;i 270 degree clockwise rotation(In-place) void rotate270(vector&S){ int N=S.size(); for(int i=0;i struct segtree{ public: segtree() : segtree(0){} explicit segtree(int n) : segtree(vector(n,e())){} explicit segtree(const vector&v) : _n(int(v.size())){ size=1; while(size<_n)size<<=1; d=vector (2*size,e()); for(int i=0;i<_n;i++)d[size+i]=v[i]; for(int i=size-1;i>=1;i--)update(i); } void set(int p,S x){ assert(0<=p&&p<_n); p+=size; d[p]=x; while(p>>=1)update(p); } S get(int p)const{ assert(0<=p&&p<_n); return d[p+size]; } S prod(int l,int r)const{ assert(0<=l&&l<=r&&r<=_n); S sml = e(),smr = e(); l+=size;r+=size; while(l>=1; r>>=1; } return op(sml,smr); } S all_prod() const {return d[1];} template int max_right(int l)const{ return max_right(l,[](S x){return f(x);}); } template int max_right(int l,F f)const{ assert(0<=l&&l<=_n); assert(f(e())); if(l==_n)return _n; l+=size; S sm=e(); do{ while(l%2==0)l>>=1; if(!f(op(sm,d[l]))){ while(l int min_left(int r) const{ return min_left(r,[](S x){return f(x);}); } template int min_left(int r,F f)const{ assert(0<=r&&r<=_n); assert(f(e())); if(r==0)return 0; r+=size; S sm=e(); do{ r--; while(r>1&&(r%2))r>>=1; if(!f(op(d[r],sm))){ while(r d; void update(int k){ d[k]=op(d[2*k],d[2*k+1]); } }; template struct fenwick_tree{ int n;vectordata; fenwick_tree(int n):n(n),data(n+1,0){} //A[p]+=x void add(int p,T x){ for(p++;p<=n;p+=p&-p){ data[p]+=x; } } //A[0]+...+A[r-1] T sum(int r){ T res=0; for(;r>0;r-=r&-r){ res+=data[r]; } return res; } // A[l]+...+A[r-1] T sum(int l,int r){ return sum(r)-sum(l); } //fenwick_tree fw(N); //fw.add(3,10); //A[3]+=10; //cout << fw.sum(2,6)< struct Comb{ vector fact,ifact; Comb(int N):fact(N+1),ifact(N+1){ fact[0]=1; for(int i=1;i<=N;i++){ fact[i]=fact[i-1]*i; } ifact[N]=fact[N].inv(); for(int i=N;i>=1;i--){ ifact[i-1]=ifact[i]*i; } } // nCr mint C(int n,int r){ if(r<0||n; using vb = vector; using vll = vector; using vs = vector; using vvi = vector>; using vvll = vector>; using vvb = vector>; using pii = pair; template using pq = priority_queue; template using pq_gt = priority_queue, greater>; template inline bool chmin(T& a, T b) { if (a > b) { a = b;return true; }return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b;return true; }return false; } const ll INF = 1LL << 60; //上右下左 const int dy4[4]={-1,0,1,0}; const int dx4[4]={0,1,0,-1}; //左上、上、右上、右、右下、下、左下、左 const int dy8[8]={-1,-1,-1,0,1,1,1,0}; const int dx8[8]={-1,0,1,1,1,0,-1,-1}; struct Sieve{ int n;vectorf,primes; Sieve(int n=1):n(n),f(n+1){ f[0]=f[1]=-1; for(long long i=2;i<=n;i++){ if(f[i])continue; primes.push_back(i); f[i]=i; for(long long j=i*i;j<=n;j+=i){ if(!f[j])f[j]=i; } } } bool isPrime(int x){return f[x]==x;} vector factorList(int x){ vector res; while(x!=1){ res.push_back(f[x]); x/=f[x]; } return res; } vector> factor(int x){ vector fl = factorList(x); if(fl.size()==0)return {}; vector> res(1,pair(fl[0],0)); for(int p:fl){ if(res.back().first==p){ res.back().second++; }else{ res.emplace_back(p,1); } } return res; } vector> factor(long long x){ vector> res; for(int p:primes){ int y =0; while(x%p==0)x/=p,++y; if(y!=0)res.emplace_back(p,y); } if(x!=1)res.emplace_back(x,1); return res; } }; ll pw(ll x,ll p){ ll res=1; rep(i,p)res*=x; return res; } //////////////////// int op(int a,int b){ return max(a,b); } int e(){ return -1; } int v; bool f(int seg_val){return seg_val> N; bool ok=false; rep(i,N.size()-1){ if(ok==true){ cout << 5; }else{ if(N[i]-'0'<=3){ ok=true; continue; }else{ if(N[i]-'0'==4){ if(N[i+1]-'0'<=3){ continue; ok=true; }else{ cout <<4; } } if(N[i]-'0'==5){ if(N[i+1]-'0'<=3){ cout << 4; ok=true; continue; }else{ cout << 5; } } } } } if(ok){ cout << 5; }else{ cout << 4; } return 0; } //--- //Comb//Comb com(N); //comb.C(n,r);nCr//comb.C(n,r).val() nCr //--- //vs S//rotate90(S)//rotate270(S) //--- //dy4,dx4//上右下左//dy8,dx8左上から時計回り //--- //Sieve sv(N);//N以下の素数を前計算 //sv.isPrime(x);//xが素数か //sv.factorList(x);//素因数を重複込みで返す //sv.factor(x);//素因数分解を(p,指数)で返す。 //auto v = sv.factor(360) -> v = {{2,3}{3,2}{5,1}}