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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/* SuffixArray (Source: 蟻本) */

//O(N log^2 N)
//pos[i] := 接頭辞の開始位置
//lcp[i] := lcp(s[pos[i]:n-1], s[pos[i-1]:n-1])
struct SuffixArray{
  vector<int> pos, lcp;

  SuffixArray(const char *S){
    int n = strlen(S), k;
    vector<int> rank(S, S+n), tmp(n);
    auto comp = [&](const int &i, const int &j){
                  if (rank[i] != rank[j]) return rank[i] < rank[j];
                  return (i+k < n ? rank[i+k] : -1) < (j+k < n ? rank[j+k] : -1);
                };

    pos.resize(n);
    iota(pos.begin(), pos.end(), 0);

    for(k=1;k<n;k*=2){
      sort(pos.begin(), pos.end(), comp);
      tmp[pos[0]] = 0;
      for(int i=1;i<n;i++)
        tmp[pos[i]] = tmp[pos[i-1]] + comp(pos[i-1], pos[i]);
      for(int i=0;i<n;i++)
        rank[i] = tmp[i];
    }

    //LongestCommonPrefixArray
    lcp.resize(n);
    for(int i=0;i<n;i++) rank[pos[i]] = i;

    for(int i=0, h=0; i<n; i++) {
      if(rank[i] + 1 < n) {
        for(int j = pos[rank[i] + 1]; max(i, j) + h < n && S[i + h] == S[j + h]; h++);
        lcp[rank[i] + 1] = h;
        if(h > 0) h--;
      }
    }
  }

  int operator[](int k) const {
    return pos[k];
  }
};

/* SimpleSegTree(0-index) */

template <typename Type = int>
struct SimpleSegTree{
  int segn2;
  Type initVal;
  vector<Type> data;
  function<Type(Type, Type)> merge;

  SimpleSegTree(int n, Type initVal, function<Type(Type, Type)> merge):
    initVal(initVal), merge(merge)
  {
    for(segn2=1; segn2<n; segn2*=2);
    data.assign(segn2*2, initVal);
  }

  SimpleSegTree(int n): //RangeMinimunQuery
    SimpleSegTree(n, INF, [](Type a, Type b){ return min(a, b); }) {}

  SimpleSegTree(int n, Type initVal): //RangeMinimunQuery
    SimpleSegTree(n, initVal, [](Type a, Type b){ return min(a, b); }) {}

  //get value [a,b)
  Type query(int a, int b, int l = 0, int r = -1, int k = 0){
    if(r == -1) r = segn2;
    if(a <= l && r <= b) return data[k];
    if(r <= a || b <= l) return initVal;
    return merge(query(a,b,l,(l+r)/2,k*2+1),query(a,b,(l+r)/2,r,k*2+2));
  }

  //set kth number x
  void set(int k, Type x){
    k += segn2-1;
    data[k] = x;
    while(k > 0){
      k = (k-1)/2;
      data[k] = merge(data[k*2+1], data[k*2+2]);
    }
  }
};

int dic[SIZE];

int dp[SIZE];

int main(){
  char ST[SIZE * 2];
  int N, M, K;



  scanf("%s", ST);
  N = strlen(ST);
  ST[N] = '#';
  scanf("%s", ST+N+1);
  M = strlen(ST) - N - 1;

  scanf("%d", &K);

  SuffixArray sa(ST);
  SimpleSegTree<int> seg(N+M+1);

  debug(N+M+1);

  set<int> ss;

  for(int i=0; i<N+M+1; i++) {
    if(sa.pos[i] > N) {
      ss.insert(i);
      //ss[i] = sa.pos[i];
    } else {
      dic[sa.pos[i]] = i;
    }
    seg.set(i, sa.lcp[i]);
    debug(sa.lcp[i]);
  }


  dp[0] = 1;
  dp[1] = -1;

  for(int i=0; i<N; i++) {
    auto it = ss.lower_bound(dic[i]);

    if(dp[i] == 0) continue;

    int l, r;

    int maxLen = 0;

    if(it != ss.end()) {
      r = *it;
      maxLen = max(maxLen, seg.query(dic[i]+1, r+1));
    }

    if(it != ss.begin()) {
      it--;
      l = *it;
      maxLen = max(maxLen, seg.query(l+1, dic[i]+1));
    }

    if (maxLen >= K) {
      dp[i+K] += 1;
      dp[i+maxLen+1] -= 1;
    }


    dp[i+1] += dp[i];
    debug(dp[i]);

    debug(ST+i);
    debug(maxLen);
  }

  if(dp[N]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }


  return 0;
}