OIG XIV - krz

// https://szkopul.edu.pl/problemset/problem/KZWEKxxWPWTihyNBSwFC8ZQw/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 1000 * 1001, K = 27, M = 11;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

std::map<std::string, std::string> m1;
std::map<std::string, int> memo;

const int m = 1e9 + 9, p = 31;

int compute_hash(const string& s) {
    int hash_value = 0;
    int p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

struct Trie {
    int next[K];
    int ns = 0;
    char c = 0;
    int parent = -1;

    Trie() { std::fill(std::begin(next), std::end(next), -1); }
};

std::vector<Trie> trie[M];

void add_string(const std::string& s) {
    int v = 0, index = s.size();
    for (const auto& ch : s) {
        int c = ch - 'a';
        if (trie[index][v].next[c] == -1) {
            trie[index][v].next[c] = trie[index].size();
            trie[index].emplace_back();
            trie[index][trie[index][v].next[c]].parent = v;
            trie[index][trie[index][v].next[c]].c = ch;
        }
        v = trie[index][v].next[c];
    }
    trie[index][v].ns++;
}

int fi = 0;
std::string s_local;
bool rt = false;
int _count_helper(int v, int pos) {
    if (v == -1) return 0;
    const int index = s_local.size();
    if (pos >= index) {
        // fi = v;
        return rt ? v : trie[index][v].ns;
    }
    const int c = s_local[pos] - 'a';

    if (s_local[pos] == '?') {
        int sum = 0;
        for (int i = 0; i < K; i++) {
            sum += _count_helper(trie[index][v].next[i], pos + 1);
        }
        return sum;
    } else {
        return _count_helper(trie[index][v].next[c], pos + 1);
    }
}

int _count(const std::string& s) {
    s_local = s;
    rt = false;
    return _count_helper(0, 0);
}

std::string get_string(const std::string& s) {
    rt = true;
    int v = _count_helper(0, 0);
    rt = false;
    const int index = s.size();

    std::string r{""};

    while (trie[index][v].parent >= 0) {
        r += trie[index][v].c;
        v = trie[index][v].parent;
    }

    std::reverse(r.begin(), r.end());

    return r;
}

void solve() {
    for (int i = 0; i < M; i++) {
        trie[i].emplace_back();
    }

    int n;
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;

        add_string(s);
    }

    int q;
    std::cin >> q;

    for (; q > 0; q--) {
        std::string s;
        std::cin >> s;

        int x = memo[s];
        if (x > 1)
            std::cout << x << '\n';
        else if (x == -1)
            std::cout << "0\n";
        else if (x == 1)
            std::cout << m1[s] << '\n';
        else {
            int w = _count(s);
            memo[s] = w;
            if (w == 0) memo[s] = -1;
            if (w == 1) {
                m1[s] = get_string(s);
                std::cout << m1[s] << '\n';
                continue;
            }

            std::cout << w << '\n';
        }
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}