#ifdef DEBUG #include"stdlibrary.h" #else #pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; #endif // #include // #include // #include // using namespace __gnu_pbds; // #include // namespace multiprecisioninteger = boost::multiprecision; // using cint=multiprecisioninteger::cpp_int; using ll=long long; using datas=pair; using ddatas=pair; using tdata=pair; using vec=vector; using mat=vector; using pvec=vector; using pmat=vector; // using llset=tree,rb_tree_tag,tree_order_statistics_node_update>; #define For(i,a,b) for(i=a;i<(ll)b;++i) #define bFor(i,b,a) for(i=b,--i;i>=(ll)a;--i) #define rep(i,N) For(i,0,N) #define rep1(i,N) For(i,1,N) #define brep(i,N) bFor(i,N,0) #define brep1(i,N) bFor(i,N,1) #define all(v) (v).begin(),(v).end() #define allr(v) (v).rbegin(),(v).rend() #define vsort(v) sort(all(v)) #define vrsort(v) sort(allr(v)) #define uniq(v) vsort(v),(v).erase(unique(all(v)),(v).end()) #define endl "\n" #define popcount __builtin_popcountll #define eb emplace_back #define print(x) cout< ostream& operator<<(ostream& os,const pair& p){return os<<"("< ostream& operator<<(ostream& os,const vector& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< ostream& operator<<(ostream& os,const set& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< ostream& operator<<(ostream& os,const multiset& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< ostream& operator<<(ostream& os,const map& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< inline bool chmax(T& a,const T b){bool x=a inline bool chmin(T& a,const T b){bool x=a>b;if(x)a=b;return x;} #ifdef DEBUG void debugg(){cout<void debugg(const T& x,const Args&... args){cout<<" "<sync_with_stdio(0); cout<size;--i)modncrlistm[i-1]=modncrlistm[i]*i%mod; } return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod; } ll modpow(ll a,ll n,const ll m=mod){ if(n<0)return 0; ll res=1; while(n>0){ if(n&1)res=res*a%m; a=a*a%m; n>>=1; } return res; } constexpr ll gcd(const ll a,const ll b) noexcept{return (!b)?abs(a):(a%b==0)?abs(b):gcd(b,a%b);} constexpr ll lcm(const ll a,const ll b) noexcept{return a/gcd(a,b)*b;} struct stringalgorithm{ public: static vector suffix_array(const vector& s,int upper){ assert(0<=upper); for(int d:s){ assert(0<=d&&d<=upper); } auto sa=sa_is(s,upper); return sa; } template static vector suffix_array(const vector& s){ int n=int(s.size()); vector idx(n); iota(idx.begin(),idx.end(),0); sort(idx.begin(),idx.end(),[&](int l,int r){return s[l] s2(n); int now=0; for(int i=0;i suffix_array(const string& s){ int n=int(s.size()); vector s2(n); for(int i=0;i static vector lcp_array(const vector& s,const vector& sa){ int n=int(s.size()); assert(n>=1); vector rnk(n); for(int i=0;i lcp(n-1); int h=0; for(int i=0;i0)--h; if(rnk[i]==0)continue; for(int j=sa[rnk[i]-1];j+h lcp_array(const string& s,const vector& sa){ int n=int(s.size()); vector s2(n); for(int i=0;i static vector z_algorithm(const vector& s){ int n=int(s.size()); if(n==0)return{}; vector z(n); z[0]=0; for(int i=1,j=0;i z_algorithm(const string& s){ int n=int(s.size()); vector s2(n); for(int i=0;i sa_naive(const vector& s){ int n=int(s.size()); vector sa(n); iota(sa.begin(),sa.end(),0); sort(sa.begin(),sa.end(),[&](int l,int r){ if(l==r)return false; while(l sa_doubling(const vector& s){ int n=int(s.size()); vector sa(n),rnk=s,tmp(n); iota(sa.begin(),sa.end(),0); for(int k=1;k static vector sa_is(const vector& s,int upper){ int n=int(s.size()); if(n==0)return{}; if(n==1)return{0}; if(n==2){ if(s[0] sa(n); vector ls(n); for(int i=n-2;i>=0;--i){ ls[i]=(s[i]==s[i+1])?ls[i+1]:(s[i] sum_l(upper+1),sum_s(upper+1); for(int i=0;i& lms){ fill(sa.begin(),sa.end(),-1); vector buf(upper+1); copy(sum_s.begin(),sum_s.end(),buf.begin()); for(auto d:lms){ if(d==n)continue; sa[buf[s[d]]++]=d; } copy(sum_l.begin(),sum_l.end(),buf.begin()); sa[buf[s[n-1]]++]=n-1; for(int i=0;i=1&&!ls[v-1]){ sa[buf[s[v-1]]++]=v-1; } } copy(sum_l.begin(),sum_l.end(),buf.begin()); for(int i=n-1;i>=0;--i){ int v=sa[i]; if(v>=1&&ls[v-1]){ sa[--buf[s[v-1]+1]]=v-1; } } }; vector lms_map(n+1,-1); int m=0; for(int i=1;i lms; lms.reserve(m); for(int i=1;i sorted_lms; sorted_lms.reserve(m); for(int v:sa){ if(lms_map[v]!=-1)sorted_lms.push_back(v); } vector rec_s(m); int rec_upper=0; rec_s[lms_map[sorted_lms[0]]]=0; for(int i=1;i(rec_s,rec_upper); for(int i=0;i // using mint=atcoder::modint998244353; // void operator>>(istream& is,mint& v){long long x;is>>x;v=x;} // ostream& operator<<(ostream& os,const mint& v){return os<sync_with_stdio(0); cin>>N>>K; ll i; vec a(N),b(N); rep(i,N)cin>>a[i]; rep(i,N)cin>>b[i]; if(multiset(all(a))!=multiset(all(b))||(N=K){ printyes; return 0; } if(N==K){ printno; return 0; } vec ch=b; ch.emplace_back(-1); vec ch2=ch; rep(i,2)for(auto x:a)ch.emplace_back(x); rep(i,2)for(auto x:ra)ch2.emplace_back(x); auto z=stringalgorithm::z_algorithm(ch); auto z2=stringalgorithm::z_algorithm(ch2); if(max(*max_element(z.begin()+1,z.end()),*max_element(z2.begin()+1,z2.end()))==N){ printyes; }else{ printno; } }