Uolevi has just had an appointment with their doctor, and there came bad news: he has been diagnosed with zetaphobia—the extreme, irrational fear of the letter Z. Unfortunately, it was again time for another Competitive Programming course contest, and this week features string algorithms. Looking at the Bu**words problem, Uolevi thought it was all dead end for him, since there wasn’t any other way but to implement the dreadful Z Algorithm.

Wait, no. Uolevi’s just come up with an idea. What if, for each buzzword, we hashed every substring of s that has the same length as the buzzword’s, comparing to the buzzword’s hash and counting every time the hashes match? What a wonderful idea!

The system kept giving WAs to Uolevi’s code though. Help him before he flips the table.

Input

• No input

Output

Your program should output a test case where the solution fails.

Constraints (of your output)

• 1 \leq |s| \leq 1000
• 1 \leq q \leq 10^5
• 1 \leq Q \leq 2 \times 10^5
• buzz_i \neq buzz_j if i \neq j
• 1 \leq |buzz_i| \leq |s|
• buzz_i consist only of lowercase Latin letters and spaces.
• None of the strings begin or end with a space.
• None of the strings contain adjacent spaces.

Uolevi's code

#include <iostream>
#include <vector>
#define MOD 123456789
#define BASE 256
#define ll long long

using namespace std;

string s, word, nothing;
int q;
int ans = 0;

ll get_hash(const string &s, const int &start, const int &end) {
    ll hash = 0;
    for (int i = start; i < end; i++)
        hash = (hash * BASE % MOD + s[i]) % MOD;
    return hash;
}

ll fast_pow(const ll &a, const ll &b) {
    if (!b) return 1;
    ll half = fast_pow(a, b >> 1);
    if (b & 1) return half * half % MOD * a % MOD;
    return half * half % MOD;
}

int main() {
    getline(cin, s);
    cin >> q;
    getline(cin, nothing); // Empties buffer for next getline

    while (q--) {
        getline(cin, word);

        ll l = 0;
        ll r_next = word.length();
        const int n = word.length() - 1;
        ll base_pow_n = fast_pow(BASE, n);

        ll word_hash = get_hash(word, 0, word.length());
        ll current_hash = get_hash(s, l, r_next);
        if (current_hash == word_hash) ans++;

        while (r_next < s.length()) {
            
            // Shifts hash by one position:
            // Hash(l+1, r+1) = (Hash(l, r) - BASE^n * s_l) * BASE + s_{r+1}

            current_hash = (current_hash - base_pow_n * s[l]) * BASE % MOD;
            current_hash = (current_hash + s[r_next] + MOD) % MOD;

            if (current_hash == word_hash) ans++;

            l++;
            r_next++;
        }
    }

    cout << ans;
}