Problem: F: Substring decomposition

problem

Given the two strings S and T and the integer k. Considering consecutive substrings of length k or more of T, determine if S can be constructed by concatenating them.

Where the string s = s_1 s_2 ... s_n is a contiguous substring s [l, r] = s_l s_ {l + 1} ... s_r (1 \ leq l \ leq r \ leq n) , S refers to a character string created by cutting out the l-th to r-th characters of s, and its length is r --l + 1.

Input format


S
T
k


Constraint

* S and T consist of lowercase alphabets
* 1 \ leq | S |, | T | \ leq 2 \ times 10 ^ 5
* 1 \ leq k \ leq | T |



Output format

Print `Yes` when S can be configured, and` No` on one line otherwise.

Input example 1


abracadabra
cadabra
Four


Output example 1


Yes

You can construct `abracadabra` by concatenating` abra` and `cadabra`, which are substrings of T with a length of 4 or more, which is a string equal to S.

Input example 2


abcd
zcba
1


Output example 2


No

Input example 3


abc
zcba
1


Output example 3


Yes

Input example 4


abcdefg
abcddefg
Four


Output example 4


No





Example

Input

abracadabra
cadabra
4


Output

Yes

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

struct SuffixArray{
  string s;
  vector<int> sa,rev;

  SuffixArray(){}
  SuffixArray(const string &S):s(S){
    int n=s.size();
    s.push_back('$');
    sa.resize(n+1);
    iota(sa.begin(),sa.end(),0);
    sort(sa.begin(),sa.end(),
         [&](int a,int b){
           if(s[a]==s[b]) return a>b;
           return s[a]<s[b];
         });
    vector<int> c(n+1,0),r(n+1),cnt(n+1);
    for(int i=0;i<=n;i++) r[i]=s[i];
    for(int len=1;len<=n;len*=2){
      for(int i=0;i<=n;i++){
        c[sa[i]]=i;
        if(i>0 &&
           r[sa[i-1]]==r[sa[i]] &&
           sa[i-1]+len<=n &&
           r[sa[i-1]+len/2]==r[sa[i]+len/2]) c[sa[i]]=c[sa[i-1]];
      }
      iota(cnt.begin(),cnt.end(),0);
      copy(sa.begin(),sa.end(),r.begin());
      for(int i=0;i<=n;i++){
        int s1=r[i]-len;
        if(s1>=0) sa[cnt[c[s1]]++]=s1;
      }
      c.swap(r);
    }
    rev.resize(n+1);
    for(int i=0;i<=n;i++) rev[sa[i]]=i;
  }
  int operator[](int i) const{return sa[i];}

  bool lt_substr(string &t,int si,int ti){
    int sn=s.size(),tn=t.size();
    while(si<sn&&ti<tn){
      if(s[si]<t[ti]) return 1;
      if(s[si]>t[ti]) return 0;
      si++;ti++;
    }
    return si==sn&&ti<tn;
  }

  int lower_bound(string& t){
    int l=0,r=s.size();
    while(l+1<r){
      int m=(l+r)>>1;
      if(lt_substr(t,sa[m],0)) l=m;
      else r=m;
    }
    return r;
  }

  int upper_bound(string& t){
    t.back()++;
    int res=lower_bound(t);
    t.back()--;
    return res;
  }

  // O(|T|*log|S|)
  int count(string& T){
    return upper_bound(T)-lower_bound(T);
  }
};


struct LongestCommonPrefix{
  SuffixArray sa;

  vector<int> ht;
  vector< vector<int> > dat;
  LongestCommonPrefix(string &s):sa(s){
    int n=s.size();
    vector<int> lcp(n,0);

    int t=0;
    lcp[0]=0;
    for(int i=0;i<n;i++){
      int j=sa[sa.rev[i]-1];
      if(t>0) t--;
      for(;j+t<n&&i+t<n;t++){
        if(sa.s[j+t]!=sa.s[i+t]) break;
      }
      lcp[sa.rev[i]-1]=t;
    }

    int h=1;
    while((1<<h)<n) h++;
    dat.assign(h,vector<int>(n));
    ht.assign(n+1,0);
    for(int j=2;j<=n;j++) ht[j]=ht[j>>1]+1;

    for(int j=0;j<n;j++) dat[0][j]=lcp[j];
    for(int i=1,p=1;i<h;i++,p<<=1)
      for(int j=0;j<n;j++)
        dat[i][j]=min(dat[i-1][j],dat[i-1][min(j+p,n-1)]);
  }

  // a, b are indices for suffix array
  int query(int a,int b){
    assert(a!=b);
    if(a>b) swap(a,b);
    int l=b-a;
    return min(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]);
  }

  // a, b are indices for string
  int lcp(int a,int b){
    return query(sa.rev[a],sa.rev[b]);
  }
};


template <typename E>
struct SegmentTree{
  using H = function<E(E,E)>;
  int n,height;
  H h;
  E ei;
  vector<E> laz;
  SegmentTree(H h,E ei):h(h),ei(ei){}
  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    laz.assign(2*n,ei);
  }
  inline void eval(int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    laz[k]=ei;
  }
  inline void thrust(int k){
    for(int i=height;i;i--) eval(k>>i);
  }
  void update(int a,int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
  }
  E get_val(int a){
    thrust(a+=n);
    return laz[a];
  }
  void set_val(int a,E x){
    thrust(a+=n);
    laz[a]=x;
  }
};

//INSERT ABOVE HERE
signed main(){
  string s,t;
  cin>>s>>t;

  string b=s+'%'+t;
  LongestCommonPrefix lcp(b);

  int n=s.size(),m=t.size();

  set<int> ss;
  for(int i=0;i<=n+1+m;i++){
    if(!isalpha(b[lcp.sa[i]])) continue;
    if(n<lcp.sa[i]) ss.emplace(i);
  }

  vector<int> nx(n+1,-1);
  for(int i=0;i<=n+1+m;i++){
    if(!isalpha(b[lcp.sa[i]])) continue;
    int k=lcp.sa[i];
    if(k>=n) continue;

    auto it=ss.upper_bound(i);
    if(it!=ss.end()) chmax(nx[k],lcp.query(i,*it));
    if(it!=ss.begin()) it--;
    if(it!=ss.end()) chmax(nx[k],lcp.query(i,*it));
  }

  int len;
  cin>>len;

  auto h=[&](int a,int b){return a||b;};
  int ei=0;
  SegmentTree<int> seg(h,ei);
  seg.init(n+m+1000);

  seg.set_val(0,1);
  for(int i=0;i<n;i++){
    if(!seg.get_val(i)) continue;
    if(nx[i]<len) continue;
    int nl=i+len;
    int nr=i+nx[i]+1;
    seg.update(nl,nr,1);
  }

  cout<<(seg.get_val(n)?"Yes":"No")<<endl;
  return 0;
}