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;

struct Suffix_Array {
  string str;
  int strlen, nowlen;
  vector<long long> rank, tmp, sa, lcp;
  Suffix_Array(string news = "", bool reqlcp = 0) {
    str = news;
    strlen = str.size();
    nowlen = 0;
    rank.resize(strlen + 1);
    tmp.resize(strlen + 1);
    sa.resize(strlen + 1);
    constuct_sa();
    if(reqlcp) constuct_lcp();
  }

  void constuct_sa() {
    auto cmp = [&](int l, int r) {
      if(rank[l] != rank[r]) return rank[l] < rank[r];
      int rx = l + nowlen <= strlen ? rank[l + nowlen] : -1;
      int ly = r + nowlen <= strlen ? rank[r + nowlen] : -1;
      return rx < ly;
    };

    for(int i = 0; i <= strlen; ++i) {
      sa[i] = i;
      rank[i] = i < strlen ? str[i] : -1;
    }
    for(nowlen = 1; nowlen <= strlen; nowlen *= 2) {
      sort(sa.begin(), sa.end(), cmp);
      tmp[sa[0]] = 0;
      for(int i = 1; i <= strlen; ++i)
        tmp[sa[i]] = tmp[sa[i - 1]] +
                     (cmp(sa[i - 1], sa[i]) ? 1 : 0);
      for(int i = 0; i <= strlen; ++i) rank[i] = tmp[i];
    }
  }
  // Longest Common Prefix Array
  void constuct_lcp() {
    lcp.resize(strlen + 1);
    for(int i = 0; i <= strlen; ++i) rank[sa[i]] = i;
    int h = 0;
    lcp[0] = 0;
    for(int i = 0; i < strlen; ++i) {
      int j = sa[rank[i] - 1];
      if(h > 0) --h;
      for(; j + h < strlen && i + h < strlen; ++h)
        if(str[j + h] != str[i + h]) break;
      lcp[rank[i] - 1] = h;
    }
  }

  bool contain(string &nowt) {
    int lef = 0, righ = strlen, tsize = nowt.size();
    while(righ - lef > 1) {
      int mid = (lef + righ) / 2;
      if(str.compare(sa[mid], tsize, nowt) < 0)
        lef = mid;
      else
        righ = mid;
    }
    return str.compare(sa[righ], tsize, nowt) == 0;
  }
};

string s, t, st;
long long k;
Suffix_Array suf;
vector<long long> dp, memo;

bool solve();

int main() {
  cin >> s >> t >> k;
  if(solve())
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

bool solve() {
  long long ssize = s.size(), stsize;
  st = s + "#" + t;
  stsize = st.size();
  suf = Suffix_Array(st, 1);
  memo.assign(s.size(), 0);
  long long now = 0;
  for(int i = 0; i <= stsize; ++i) {
    if(suf.sa[i] < ssize) {
      memo[suf.sa[i]] = max(memo[suf.sa[i]], now);
      now = min(now, suf.lcp[i]);
    }
    else
      now = suf.lcp[i];
  }
  now = 0;
  for(int i = stsize; i >= 1; --i) {
    if(suf.sa[i] < ssize) {
      memo[suf.sa[i]] = max(memo[suf.sa[i]], now);
      now = min(now, suf.lcp[i - 1]);
    }
    else
      now = suf.lcp[i - 1];
  }
  dp.assign(s.size() + 2, 0);
  dp[0] = 1;
  dp[1] = -1;
  for(int i = 0; i <= ssize; ++i) {
    if(i != 0) dp[i] += dp[i - 1];
    if(i == ssize || memo[i] < k || dp[i] == 0) continue;
    ++dp[i + k];
    --dp[min(i + memo[i] + 1, ssize + 1)];
  }
  return dp[ssize] > 0;
}