#include <bits/stdc++.h>

using namespace std;

#define int long long
// #define double long double
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define bitcnt(x) __builtin_popcount(x)
#define lbit(x) __builtin_ffsll(x)
#define rbit(x) __builtin_clzll(x)
#define SZ(x) ((long long)(x).size())
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
#define rAll(a) (a).rbegin(), (a).rend()
#define cinfast() cin.tie(0), ios::sync_with_stdio(false)
#define PERM(c)                                                                \
    sort(All(c));                                                              \
    for(bool cp = true; cp; cp = next_permutation(All(c)))
#define MKORDER(n)                                                             \
    vector<int> od(n);                                                         \
    iota(All(od), 0LL);

template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CCIN(...)                                                              \
    char __VA_ARGS__;                                                          \
    CIN(__VA_ARGS__)
#define DCIN(...)                                                              \
    double __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    long long __VA_ARGS__;                                                     \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v)                                                              \
    {                                                                          \
        FOREACH(x, v) { cout << x << " "; }                                    \
        cout << "\n";                                                          \
    }
template <typename T = string> inline void eputs(T s) {
    cout << s << "\n";
    exit(0);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *)array, (T *)(array + N), val);
}

template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using PQ = priority_queue<T>;

typedef long long ll;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<ll, ll> PL;
typedef vector<PL> VPL;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;
const double PI = atan(1.0) * 4.0;
const ll dw[] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dh[] = {0, 1, 1, 1, 0, -1, -1, -1};
#define PI 3.141592653589793238

template <size_t X> struct Trie {
    struct Node {
        char c;
        array<int, X> nxt;
        vector<int> idxs;
        int idx;
        Node(char c) : c(c), idx(-1) { fill(nxt.begin(), nxt.end(), -1); }
    };

    using F = function<int(char)>;
    vector<Node> vs;
    F conv;

    Trie(F conv, char c = '$') : conv(conv) { vs.emplace_back(c); }

    inline int &next(int i, int j) { return vs[i].nxt[j]; }

    void add(const string &s, int x) {
        int pos = 0;
        for(int i = 0; i < (int)s.size(); i++) {
            int k = conv(s[i]);
            if(~next(pos, k)) {
                pos = next(pos, k);
                continue;
            }
            int npos = vs.size();
            next(pos, k) = npos;
            vs.emplace_back(s[i]);
            pos = npos;
        }
        vs[pos].idx = x;
        vs[pos].idxs.emplace_back(x);
    }

    //文字列丸ごと検索
    int find(const string &s) {
        int pos = 0;
        for(int i = 0; i < (int)s.size(); i++) {
            int k = conv(s[i]);
            if(next(pos, k) < 0) return -1;
            pos = next(pos, k);
        }
        return idx(pos);
    }

    //頂点移動
    int move(int pos, char c) {
        assert(pos < (int)vs.size());
        return pos < 0 ? -1 : next(pos, conv(c));
    }

    //子供の数
    int size() { return vs.size(); }

    int idx(int pos) { return pos < 0 ? -1 : vs[pos].idx; }

    //対応するパターンのindex
    vector<int> idxs(int pos) { return pos < 0 ? vector<int>() : vs[pos].idxs; }
};

template <size_t X> struct AhoCorasick : Trie<X + 1> {
    using TRIE = Trie<X + 1>;
    using TRIE::next;
    using TRIE::TRIE;
    vector<int> cnt;

    void build(int heavy = true) {
        auto &vs = TRIE::vs;
        int n = vs.size();
        cnt.resize(n);
        for(int i = 0; i < n; i++) {
            if(heavy) sort(vs[i].idxs.begin(), vs[i].idxs.end());
            cnt[i] = vs[i].idxs.size();
        }

        queue<int> que;
        for(int i = 0; i < (int)X; i++) {
            if(~next(0, i)) {
                next(next(0, i), X) = 0;
                que.emplace(next(0, i));
            } else {
                next(0, i) = 0;
            }
        }

        while(!que.empty()) {
            auto &x = vs[que.front()];
            int fail = x.nxt[X];

            cnt[que.front()] += cnt[fail];
            que.pop();

            for(int i = 0; i < (int)X; i++) {
                int &nx = x.nxt[i];
                if(nx < 0) {
                    nx = next(fail, i);
                    continue;
                }
                que.emplace(nx);
                next(nx, X) = next(fail, i);
                if(heavy) {
                    auto &idx = vs[nx].idxs;
                    auto &idy = vs[next(fail, i)].idxs;
                    vector<int> idz;
                    set_union(idx.begin(), idx.end(), idy.begin(), idy.end(), back_inserter(idz));
                    idx = idz;
                }
            }
        }
    }

    vector<int> match(string s, int heavy = true) {
        auto &vs = TRIE::vs;
        vector<int> res(heavy ? TRIE::size() : 1);
        int pos = 0;
        for(auto &c : s) {
            pos = next(pos, TRIE::conv(c));
            if(heavy)
                for(auto &x : vs[pos].idxs) res[x]++;
            else
                res[0] += cnt[pos];
        }
        return res;
    }

    int count(int pos) { return cnt[pos]; }
};

auto f = [](char c) { return c - 'a'; };
AhoCorasick<27> aho(f);

signed main() {
    SCIN(S);
    LCIN(M);
    VS C(M);
    REP(i, M) {
        cin >> C[i];
        aho.add(C[i], i);
    }
    aho.build();
    int l = S.size();
    int pos = 0;
    ll ans = 0;
    VL vs;
    REP(i, l) {
        pos = aho.move(pos, S[i]);
        if(aho.count(pos)){
            ans++;
            pos = 0;
        }
    }
    cout << ans << "\n";
}


### Prompt

Please provide a CPP coded solution to the problem described below:

G： 検閲により置換 (Censored String)

Problem Statement

You are given the string S, and the set of strings \mathcal P whose size is N. Now we consider applying the following operation to S:

* Choose exactly one character in S, and replace it with '*'.



Let s_i be a i-th character of S, S_{ij} be a consecutive substring in S such that  S = s_i s_{i+1} $\cdots$  s_j, and p_k as the k-th string of P. Your task is to calculate the minimum number of operations for satisfying the following condition.

* For all pairs (S_{ij}, p_k), it is satisfied that S_{ij} \neq p_k.



Input

An input is given in the following format.


S
N
p_1
p_2
$\vdots$
p_N


* In line 1, you are given the string S.
* In line 2, given an integer N. N means the size of P.
* From line 3 to the end, given p_i, the i-th string of P.



Constraints

* 1 \leq |S| \leq 10^5
* 1 \leq N \leq 10^5
* 1 \leq |p_1| + |p_2| +  $\cdots$  + |p_N| \leq 10^5
* If i \neq j, it is guaranteed that p_i \neq p_j
* S, and p_i include lowercase letters only



Output

Print the minimum number of operations in one line.

Sample Input 1


brainfuck
1
fuck


Sample Output 1


1

For example, if you change "brainfuck" into "brainf*ck", you can satisfy the condition. You have to perform operation at least once, and it is the minimum value.

Sample Input 2


aaa
1
a


Sample Output 2


3

You have to operate for all characters.

Sample Input 3


hellshakeyano
3
hell
shake
key


Sample Output 3


2

In this case, for example, if you change "hellshakeyano" into "h*llsha*eyano", you can satisfy the condition. Notice if you replace one character, it might happen that several strings in the set P, which appear as the consecutive substring of S, simultaneously disappear.





Example

Input

brainfuck
1
fuck


Output

1

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

#define int long long
// #define double long double
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define bitcnt(x) __builtin_popcount(x)
#define lbit(x) __builtin_ffsll(x)
#define rbit(x) __builtin_clzll(x)
#define SZ(x) ((long long)(x).size())
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
#define rAll(a) (a).rbegin(), (a).rend()
#define cinfast() cin.tie(0), ios::sync_with_stdio(false)
#define PERM(c)                                                                \
    sort(All(c));                                                              \
    for(bool cp = true; cp; cp = next_permutation(All(c)))
#define MKORDER(n)                                                             \
    vector<int> od(n);                                                         \
    iota(All(od), 0LL);

template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CCIN(...)                                                              \
    char __VA_ARGS__;                                                          \
    CIN(__VA_ARGS__)
#define DCIN(...)                                                              \
    double __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    long long __VA_ARGS__;                                                     \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v)                                                              \
    {                                                                          \
        FOREACH(x, v) { cout << x << " "; }                                    \
        cout << "\n";                                                          \
    }
template <typename T = string> inline void eputs(T s) {
    cout << s << "\n";
    exit(0);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *)array, (T *)(array + N), val);
}

template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using PQ = priority_queue<T>;

typedef long long ll;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<ll, ll> PL;
typedef vector<PL> VPL;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;
const double PI = atan(1.0) * 4.0;
const ll dw[] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dh[] = {0, 1, 1, 1, 0, -1, -1, -1};
#define PI 3.141592653589793238

template <size_t X> struct Trie {
    struct Node {
        char c;
        array<int, X> nxt;
        vector<int> idxs;
        int idx;
        Node(char c) : c(c), idx(-1) { fill(nxt.begin(), nxt.end(), -1); }
    };

    using F = function<int(char)>;
    vector<Node> vs;
    F conv;

    Trie(F conv, char c = '$') : conv(conv) { vs.emplace_back(c); }

    inline int &next(int i, int j) { return vs[i].nxt[j]; }

    void add(const string &s, int x) {
        int pos = 0;
        for(int i = 0; i < (int)s.size(); i++) {
            int k = conv(s[i]);
            if(~next(pos, k)) {
                pos = next(pos, k);
                continue;
            }
            int npos = vs.size();
            next(pos, k) = npos;
            vs.emplace_back(s[i]);
            pos = npos;
        }
        vs[pos].idx = x;
        vs[pos].idxs.emplace_back(x);
    }

    //文字列丸ごと検索
    int find(const string &s) {
        int pos = 0;
        for(int i = 0; i < (int)s.size(); i++) {
            int k = conv(s[i]);
            if(next(pos, k) < 0) return -1;
            pos = next(pos, k);
        }
        return idx(pos);
    }

    //頂点移動
    int move(int pos, char c) {
        assert(pos < (int)vs.size());
        return pos < 0 ? -1 : next(pos, conv(c));
    }

    //子供の数
    int size() { return vs.size(); }

    int idx(int pos) { return pos < 0 ? -1 : vs[pos].idx; }

    //対応するパターンのindex
    vector<int> idxs(int pos) { return pos < 0 ? vector<int>() : vs[pos].idxs; }
};

template <size_t X> struct AhoCorasick : Trie<X + 1> {
    using TRIE = Trie<X + 1>;
    using TRIE::next;
    using TRIE::TRIE;
    vector<int> cnt;

    void build(int heavy = true) {
        auto &vs = TRIE::vs;
        int n = vs.size();
        cnt.resize(n);
        for(int i = 0; i < n; i++) {
            if(heavy) sort(vs[i].idxs.begin(), vs[i].idxs.end());
            cnt[i] = vs[i].idxs.size();
        }

        queue<int> que;
        for(int i = 0; i < (int)X; i++) {
            if(~next(0, i)) {
                next(next(0, i), X) = 0;
                que.emplace(next(0, i));
            } else {
                next(0, i) = 0;
            }
        }

        while(!que.empty()) {
            auto &x = vs[que.front()];
            int fail = x.nxt[X];

            cnt[que.front()] += cnt[fail];
            que.pop();

            for(int i = 0; i < (int)X; i++) {
                int &nx = x.nxt[i];
                if(nx < 0) {
                    nx = next(fail, i);
                    continue;
                }
                que.emplace(nx);
                next(nx, X) = next(fail, i);
                if(heavy) {
                    auto &idx = vs[nx].idxs;
                    auto &idy = vs[next(fail, i)].idxs;
                    vector<int> idz;
                    set_union(idx.begin(), idx.end(), idy.begin(), idy.end(), back_inserter(idz));
                    idx = idz;
                }
            }
        }
    }

    vector<int> match(string s, int heavy = true) {
        auto &vs = TRIE::vs;
        vector<int> res(heavy ? TRIE::size() : 1);
        int pos = 0;
        for(auto &c : s) {
            pos = next(pos, TRIE::conv(c));
            if(heavy)
                for(auto &x : vs[pos].idxs) res[x]++;
            else
                res[0] += cnt[pos];
        }
        return res;
    }

    int count(int pos) { return cnt[pos]; }
};

auto f = [](char c) { return c - 'a'; };
AhoCorasick<27> aho(f);

signed main() {
    SCIN(S);
    LCIN(M);
    VS C(M);
    REP(i, M) {
        cin >> C[i];
        aho.add(C[i], i);
    }
    aho.build();
    int l = S.size();
    int pos = 0;
    ll ans = 0;
    VL vs;
    REP(i, l) {
        pos = aho.move(pos, S[i]);
        if(aho.count(pos)){
            ans++;
            pos = 0;
        }
    }
    cout << ans << "\n";
}


```