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;

typedef long long ll;
constexpr int INF = 1<<30;

struct SuffixArray{
    int n, k;
    string s;
    vector<int> rank, tmp, sa;

    function<bool(const int&, const int&)> comp = [&](const int &i, const int &j){
        if(rank[i] != rank[j]) return rank[i] < rank[j];
        else{
            int ri = i+k <= n ? rank[i+k] : -1;
            int rj = j+k <= n ? rank[j+k] : -1;
            return ri < rj;
        }
    };
    void construct(const string &str){
        s = str;
        n = s.size();
        rank.resize(n+1);
        tmp.resize(n+1);
        sa.resize(n+1);

        for(int i=0;i<=n;i++){
            sa[i] = i;
            rank[i] = i < n ? s[i] : -1;
        }

        for(k = 1; k<=n; k<<=1){
            sort(sa.begin(), sa.begin()+n+1, comp);
            tmp[sa[0]] = 0;
            for(int i=1;i<=n;i++){
                tmp[sa[i]] = tmp[sa[i-1]] + (comp(sa[i-1],sa[i]) ? 1 : 0);
            }
            for(int i=0;i<=n;i++){
                rank[i] = tmp[i];
            }
        }
    }
    bool contain(const string &t){
        int a = 0, b = n;
        while(b-a > 1){
            int c = (a+b)/2;
            if(s.compare(sa[c], t.size(), t) < 0){
                a = c;
            }else{
                b = c;
            }
        }
        return s.compare(sa[b], t.size(), t) == 0;
    }

    int operator[] (int i) const {
        return sa[i];
    }
};

struct LCP{
    int n;
    vector<int> rank;
    vector<int> lcp;
    SuffixArray sa;

    void construct(const string &str){
        int n = str.size();
        sa.construct(str);
        rank.resize(n+1);
        lcp.resize(n);
        for(int i=0;i<=n;i++) rank[sa[i]] = i;

        int h = 0;
        for(int i=0;i<n;i++){
            int j = sa[rank[i]-1];
            if(h>0) h--;
            for(; j+h < n && i+h < n; h++){
                if(str[j+h] != str[i+h]) break;
            }
            lcp[rank[i]-1] = h;
        }
    }

    int operator[] (int i) const {
        return lcp[i];
    }
};

template <typename Monoid>
struct SegmentTree{
private:
    using F = function<Monoid(Monoid, Monoid)>;
    int N;
    vector<Monoid> node;
    F f;
    Monoid e;  // identity element

public:
    SegmentTree(){}
    SegmentTree(F f, Monoid e):f(f), e(e){}
    void init(int sz){
        N = 1;
        while(N < sz) N <<= 1;
        node.assign(2*N-1, e);
    }
    void build(vector<Monoid>& v){
        int sz = int(v.size());
        init(sz);
        for(int i=0; i<sz; i++){
            node[i+N-1] = v[i];
        }
        for(int i=N-2; i>=0; i--){
            node[i] = f(node[i*2+1], node[i*2+2]);
        }
    }
    void update(int k, Monoid x){
        k += N-1;
        node[k] = x;
        while(k > 0){
            k = (k-1)/2;
            node[k] = f(node[2*k+1], node[2*k+2]);
        }
    }
    // [a,b)
    Monoid query(int a, int b){return query(a, b, 0, 0, N);}
    Monoid query(int a, int b, int k, int l, int r){
        if(b <= l || r <= a) return e;
        if(a <= l && r <= b) return node[k];
        Monoid vl, vr;
        vl = query(a, b, 2*k+1, l, (l+r)/2);
        vr = query(a, b, 2*k+2, (l+r)/2, r);
        return f(vl, vr);
    }
};

int main(){
    int n, k;
    string s, t;
    cin >> s >> t >> k;
    n = s.size();
    s += '#' + t;
    LCP lcp;
    SuffixArray sa;
    lcp.construct(s);
    sa = lcp.sa;
    vector<int> dp(n+2), tpos;
    for(int i=0;i<=s.size();i++){
        if(sa[i] > n) tpos.push_back(i);
    }
    auto f = [&](int a, int b){return min(a,b);};
    SegmentTree<int> seg(f, INF);
    seg.build(lcp.lcp);
    dp[0] = 1;
    dp[1] = -1;
    for(int i=0;i<n;i++){
        int j = lcp.rank[i], maxi = 0;
        auto itr = lower_bound(tpos.begin(), tpos.end(), j);
        if(itr != tpos.begin()){
            auto tmp = itr;
            maxi = max(maxi, seg.query(*--tmp, j));
        }
        if(itr != tpos.end()){
            auto tmp = itr;
            maxi = max(maxi, seg.query(j, *tmp));
        }
        if(maxi >= k && dp[i] > 0){
            dp[i+k]++;
            dp[i+maxi+1]--;
        }
        dp[i+1] += dp[i];
    }
    cout << (dp[n] > 0 ? "Yes" : "No") << endl;
    return 0;
}