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;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

vector<int> construct_sa(const string& S){
  vector<int> SA, ranks, tmp;
  int N = S.length();

  SA.resize(N + 1);
  ranks.resize(N + 1);
  tmp.resize(N + 1);

  for(int i = 0; i <= N; i++){
    SA[i] = i;
    ranks[i] = (i < N ? S[i] : -1);
  }

  for(int k = 1; k <= N; k *= 2){
    auto f = [&](const int& a,const int& b){
      if(ranks[a] != ranks[b]) return ranks[a] < ranks[b];
      else{
        int ra = (a + k <= N ? ranks[a + k] : -1);
        int rb = (b + k <= N ? ranks[b + k] : -1);
        return ra < rb;
      }
    };

    sort(SA.begin(), SA.end(), f);

    tmp[SA[0]] = 0;
    for(int i = 1; i <= N; i++){
      tmp[SA[i]] = tmp[SA[i-1]] + (f(SA[i-1], SA[i]) ? 1 : 0);
    }
    for(int i = 0; i <= N; i++){
      ranks[i] = tmp[i];
    }
  }
  return SA;
}

vector<int> construct_lcp(const string& S, const vector<int>& SA){
  int N = S.length();
  vector<int> LCP(N + 1), ranks(N + 1);

  for(int i = 0; i <= N; i++){
    ranks[SA[i]] = i;
  }

  int h = 0;
  LCP[0] = 0;
  for(int i = 0; i < N; i++){
    int j = SA[ranks[i] - 1];

    if(h > 0) h--;
    while(j + h < N && i + h < N){
      if(S[j + h] != S[i + h]) break;
      h++;
    }
    int index = ranks[i] - 1;
    LCP[ranks[i] - 1] = h;
  }
  return LCP;
}

struct RangeMaxQuery{
  ll dat[(1<<21)-1];
  int size;

  void init(int n_){
    size=1;
    while(size<n_) size*=2;
    for(int i=0;i<2*size-1;i++)dat[i]=0;
  }

  void update(int k,ll a){
    k+=size-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=max(dat[k*2+1],dat[k*2+2]);
    }
  }

  ll subquery(int a,int b,int k,int l,int r){
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b)return dat[k];
    else{
      return max(subquery(a,b,k*2+1,l,(l+r)/2),subquery(a,b,k*2+2,(l+r)/2,r));
    }
  }
  
  ll query(int a,int b){
    return subquery(a,b,0,0,size);
  }
};

RangeMaxQuery sgt;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  string S,T;
  int K;
  cin>>S>>T>>K;
  int N=S.size();
  string A=S+"$"+T;

  vector<int> SA=construct_sa(A);
  vector<int> lcp=construct_lcp(A,SA);

  int M=A.size();
  vector<int> nxt(N,0);
  int crtmn=0;
  rep(i,M+1){
    if(SA[i]<N){
      maxch(nxt[SA[i]],crtmn);
      if(i<M)minch(crtmn,lcp[i]);
    }else if(SA[i]>N){
      if(i<M)crtmn=lcp[i];
    }
  }

  crtmn=0;
  for(ll i=M-1;i>=0;i--){
    if(SA[i]<N){
      maxch(nxt[SA[i]],crtmn);
      if(i-1>=0)minch(crtmn,lcp[i-1]);
    }else if(SA[i]>N){
      if(i-1>=0)crtmn=lcp[i-1];
    }
  }

  vector<bool> dp(N+1,false);
  dp[N]=true;
  sgt.init(N+1);
  sgt.update(N,1);
  for(ll i=N-1;i>=0;i--){
    if(K>nxt[i])continue;
    ll f=sgt.query(min((ll)N,i+K),min((ll)N+1,i+nxt[i]+1));
    if(f>0)dp[i]=true;
    sgt.update(i,dp[i]);
  }
  if(dp[0])cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

  return 0;
}