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 <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#define llint long long
#define mod 1000000007
#define inf 1e9

using namespace std;
typedef pair<llint, llint> P;

struct SegTree{
	int size;
	vector<int> seg;

	SegTree(){}
	SegTree(int size){
		this->size = size;
		seg.resize(1<<(size+1));
	}

	void init()
	{
		for(int i = 0; i < (1<<(size+1)); i++) seg[i] = inf;
	}

	void update(int i, int val)
	{
		i += (1 << size);
		seg[i] = val;
		while(i > 1){
			i /= 2;
			seg[i] = min(seg[i*2], seg[i*2+1]);
		}
	}

	int query(int a, int b, int k, int l, int r)
	{
		if(b < l || r < a) return inf;
		if(a <= l && r <= b) return seg[k];
		int lval = query(a, b, k*2, l, (l+r)/2);
		int rval = query(a, b, k*2+1, (l+r)/2+1, r);
		return min(lval, rval);
	}
	int query(int a, int b)
	{
		return query(a, b, 1, 0, (1<<size)-1);
	}
};

int kk, nn;
int Rank[400005];
int tmp[400005];

bool compare_sa(int i, int j)
{
	if(Rank[i] != Rank[j]) return Rank[i] < Rank[j];
	int ri, rj;
	if(i+kk <= nn) ri = Rank[i+kk]; else ri = -1;
	if(j+kk <= nn) rj = Rank[j+kk]; else rj = -1;
	return ri < rj;
}

void makeSA(string s, int sa[]){
	nn = s.size();
	for(int i = 0; i <= nn; i++) sa[i] = i;
	for(int i = 0; i < nn; i++) Rank[i] = s[i];
	s += " ";
	s[nn] = -1;

	for(kk = 1; kk <= nn; kk*=2){
		sort(sa, sa+nn+1, compare_sa);
		int val = 0;
		tmp[sa[0]] = 0;
		for(int i = 1; i <= nn; i++){
			if(compare_sa(sa[i-1], sa[i])) val++;
			tmp[sa[i]] = val;
		}
		for(int i = 0; i <= nn; i++) Rank[i] = tmp[i];
	}
}

void makeLCP(string s, int sa[], int lcp[]){
	nn = s.size();
	for(int i = 0; i <= nn; i++) Rank[sa[i]] = i;

	int h = 0;
	lcp[0] = 0;
	for(int i = 0; i < nn; i++){
		int j = sa[Rank[i]-1];
		while(i+h < nn && j+h < nn && s[i+h] == s[j+h]) h++;
		lcp[Rank[i]-1] = h;
		if(h > 0) h--;
	}
}

string s, t;
int k;
int sa[400005], lcp[400005], sa_inv[400005];
int pred[400005], succ[400005];
int dp[400005];
SegTree seg(19);

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

  cin >> s >> t;
  cin >> k;

  string S = s + "#" + t;
  makeSA(S, sa);
  makeLCP(S, sa, lcp);
  for(int i = 0; i <= S.size(); i++) sa_inv[sa[i]] = i;

  /*for(int i = 0; i <= S.size(); i++){
    cout << i << " " << S.substr(sa[i]) << " " << lcp[i] << endl;
  }*/

  int x = -1;
  for(int i = 0; i <= S.size(); i++){
    pred[i] = x;
    if(sa[i] > s.size()) x = i;
  }
  x = S.size()+1;
  for(int i = S.size(); i >= 0; i--){
    succ[i] = x;
    if(sa[i] > s.size()) x = i;
  }

  seg.init();
  for(int i = 0; i <= S.size(); i++) seg.update(i, lcp[i]);

  int n = s.size();
  s = "#" + s; int sum = 0;
  dp[0] = 1, dp[1] = -1;
  for(int i = 0; i <= n; i++){
    sum += dp[i];
    if(sum == 0) continue;
    int mx = 0, pos = sa_inv[i];
    if(pred[pos] >= 0){
      mx = max(mx, seg.query(pred[pos], pos-1));
    }
    if(succ[pos] <= S.size()){
      mx = max(mx, seg.query(pos, succ[pos]-1));
    }
    //cout << i << " " << pos << " " << pred[pos] << " " << succ[pos] << " " << mx << endl;
    if(mx < k) continue;
    dp[i+k]++, dp[i+mx+1]--;
  }
  if(sum) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}