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 ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;


const int MAX_STRING_SIZE = 1000000;

ll base = 1007;

vector<ll> MODS({2147483647, 6700417, 524287, 1000000007}

);

vector<vector<ll>> invs(MODS.size()), pows(MODS.size());

ll powm(ll e, ll x, ll m) {
  if (x == 0) return 1;
  if (x == 1) return e;
  if (x % 2 == 0) return powm((e * e) % m, x / 2, m);
  return (e * powm(e, x - 1, m)) % m;
}

void RHinit() {
  int i = 0;
  for (auto &p : MODS) {
    invs[i].resize(MAX_STRING_SIZE + 1);
    invs[i][0] = 1;
    ll inv = powm(base, p - 2, p);
    for (int j = 1; j <= MAX_STRING_SIZE; j++) {
      invs[i][j] = (invs[i][j - 1] * inv) % p;
    }
    pows[i].resize(MAX_STRING_SIZE + 1);
    pows[i][0] = 1;
    for (int j = 1; j <= MAX_STRING_SIZE; j++) {
      pows[i][j] = (pows[i][j - 1] * base) % p;
    }
    i++;
  }
}

struct RH {
  int n;
  string s;
  vector<vector<ll>> hs;

  RH(string &s) : s(s) {
    if (pows[0].empty()) {
      RHinit();
    }
    n = s.size();
    hs.resize(MODS.size());
    for (int i = 0; i < MODS.size(); i++) {
      hs[i].resize(n + 1);
      hs[i][0] = 0;
      for (int j = 0; j < n; j++) {
        hs[i][j + 1] = (hs[i][j] + pows[i][j] * s[j]) % MODS[i];
      }
    }
  }

  vector<ll> substr(int l, int r) {
    vector<ll> ret(MODS.size());
    for (int i = 0; i < MODS.size(); i++) {
      ret[i] = (hs[i][r] - hs[i][l] + MODS[i]) % MODS[i];
      ret[i] *= invs[i][l];
      ret[i] %= MODS[i];
    }
    return ret;
  }
};


template<typename T>
struct RSQRAQ2 {
  int n;
  T unit;
  function<T(T, T)> update_f, sum_f, query_f;
  vector<T> dat, lazy;

  RSQRAQ2() {}

  RSQRAQ2(int n_, T unit, function<T(T, T)> update_f, function<T(T, int)> sum_f, function<T(T, T)> query_f)
      : unit(unit), update_f(update_f), sum_f(sum_f), query_f(query_f) {
    n = 1;
    while (n < n_)
      n *= 2;
    dat.assign(n * 2, unit);
    lazy.assign(n * 2, unit);
  }

  RSQRAQ2(vector<T> v, T unit, function<T(T, T)> update_f, function<T(T, int)> sum_f, function<T(T, T)> query_f)
      : unit(unit), update_f(update_f), sum_f(sum_f), query_f(query_f) {
    n = 1;
    while (n < v.size()) n <<= 1;
    dat.assign(n * 2, unit);
    lazy.assign(n * 2, unit);
    for (int i = 0; i < v.size(); i++) {
      dat[n + i - 1] = v[i];
    }
    for (int i = n - 2; i >= 0; i--) {
      dat[i] = query_f(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }

  void eval(int len, int k) {
    if (lazy[k] == unit)
      return;
    if (k * 2 + 1 < n * 2 - 1) {
      lazy[2 * k + 1] = update_f(lazy[2 * k + 1], lazy[k]);
      lazy[2 * k + 2] = update_f(lazy[2 * k + 2], lazy[k]);
    }
    dat[k] = update_f(dat[k], sum_f(lazy[k], len));
    lazy[k] = unit;
  }

  // [a, b)
  T update(int a, int b, T x, int k, int l, int r) {
    eval(r - l, k);
    if (b <= l || r <= a)
      return dat[k];
    if (a <= l && r <= b) {
      lazy[k] = update_f(lazy[k], x);
      return query_f(dat[k], sum_f(lazy[k], r - l));
    }
    return dat[k] = query_f(update(a, b, x, 2 * k + 1, l, (l + r) / 2),
                            update(a, b, x, 2 * k + 2, (l + r) / 2, r));
  }

  T update(int a, int b, T x) { return update(a, b, x, 0, 0, n); }

  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    eval(r - l, k);
    if (b <= l || r <= a)
      return unit;
    if (a <= l && r <= b)
      return dat[k];
    return query_f(query(a, b, 2 * k + 1, l, (l + r) / 2), query(a, b, 2 * k + 2, (l + r) / 2, r));
  }

  T query(int a, int b) { return query(a, b, 0, 0, n); }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  string s, t;
  int k;
  cin >> s >> t >> k;
  if (k * 2 > s.size()) k = s.size();
  if (k > t.size()) {
    cout << "No" << endl;
    return 0;
  }
  RHinit();
  RH srh(s), trh(t);
  set<vector<ll>> ts;
  for (int i = 0; i <= t.size() - k; i++) {
    ts.insert(trh.substr(i, i + k));
  }
  RSQRAQ2<ll> r(s.size() + 2, 0, [](ll l, ll r) {
                  return l + r;
                }, [](ll l, int len) {
                  return l * len;
                }, [](ll l, ll r) {
                  return l + r;
                }
  );
  for (int i = 0; i <= s.size() - k; i++) {
    auto v = srh.substr(i, i + k);
    if (ts.find(v) != ts.end()) {
      r.update(i, i + k, 1);
    }
  }
  bool ok = true;
  for (int i = 0; i < s.size(); i++) {
    if (r.query(i, i + 1) == 0) {
      ok = false;
    }
  }

  if (ok) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}