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<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-5;
const ld pi = acos(-1.0);

struct SuffixArray {
	struct SAComp {
		const int h;
		const vector<int> &g;
		SAComp(int h, vector<int> &g) : h(h), g(g) { ; }
		bool operator() (int a, int b) {
			return a != b && (g[a] != g[b] ? g[a] < g[b] : g[a + h] < g[b + h]);
		}
	};
	int n;
	string str;
	vector<int> sa, lcp;
	SuffixArray(const string &t) : n(t.size()), sa(n + 1), lcp(n + 1) {
		str = t;
		//strcpy(str, t.c_str());
		// build SA
		vector<int> g(n + 1, 0), b(n + 1, 0);
		rep(i, n + 1) { sa[i] = i; g[i] = str[i]; }
		sort(begin(sa), end(sa), SAComp(0, g));
		for (int h = 1; b[n] != n; h *= 2) {
			SAComp comp(h, g);
			sort(sa.begin(), sa.end(), comp);
			rep(i, n) b[i + 1] = b[i] + comp(sa[i], sa[i + 1]);
			rep(i, n + 1) g[sa[i]] = b[i];
		}
		// build LCP
		int h = 0;
		rep(i, n + 1) b[sa[i]] = i;
		rep(i, n + 1) {
			if (b[i]) {
				for (int j = sa[b[i] - 1]; j + h<n && i + h<n && str[j + h] == str[i + h]; ++h);
				lcp[b[i]] = h;
			}
			else {
				lcp[b[i]] = -1;
			}
			if (h > 0) --h;
		}
	}
};
void solve() {
	string s, t; cin >> s >> t;
	string z = s + t;
	SuffixArray st(z);
	int sl = s.size(); int tl = t.size();
	vector<int> v(sl,0);
	rep(i, sl + tl+1) {
		int id = st.sa[i];
		if (id >= sl) {
			int cur = i - 1;
			if (cur >= 0) {
				int num = st.lcp[i];
				while (cur >= 0 && st.sa[cur] < sl) {
					num = min(num, st.lcp[cur+1]);
					v[st.sa[cur]] = max(v[st.sa[cur]], num);
					cur--;
				}
			}
			cur = i + 1;
			if (cur >= sl + tl+1)continue;
			int num = st.lcp[i+1];
			while (cur < sl + tl+1 && st.sa[cur] < sl) {
				num = min(num, st.lcp[cur]);
				//cout << i << " " << cur << " " << st.sa[cur] << " " << num << endl;
				v[st.sa[cur]] = max(v[st.sa[cur]], num);

				cur++;
			}
		}
	}
	//cout << z << endl;
	rep(i, sl + tl+1) {
		//cout << i<<" "<<st.sa[i]<<" "<<st.lcp[i] << endl;
	}
	rep(i, sl) {
		if (i + v[i] > sl) {
			v[i] = sl-i;
		}
		//cout << s[i]<<" "<<v[i] << endl;
	}
	vector<int> ad(sl + 1,0);
	int rest = 1;
	int k; cin >> k;
	rep(i, sl) {
		rest = max(rest, ad[i]);
		//cout << "??" << rest << endl;
		if (rest > 0) {
			int len = v[i];
			if (len >= k&&i+k<=sl) {
				ad[i + k] = max(ad[i + k], v[i] - k + 1);
			}
		}
		rest--;
		//cout <<"??"<< rest << endl;
	}
	rest = max(rest, ad[sl]);
	//cout << rest << endl;
	if (rest > 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}