image.png

image.png

#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

class Node {
public:
    unordered_map<long long, Node*> c;
    long long cnt;

    Node() {
        cnt = 0;
    }
};

class Trie {
private:
    Node* r;

public:
    Trie() {
        r = new Node();
    }

    void ins(const vector<long long>& lst) {
        Node* n = r;
        for (long long num : lst) {
            if (n->c.find(num) == n->c.end()) {
                n->c[num] = new Node();
            }
            n = n->c[num];
            n->cnt++;
        }
    }

    long long cntPref(const vector<long long>& pref) {
        Node* n = r;
        for (long long num : pref) {
            if (num == -1) continue;
            if (n->c.find(num) == n->c.end()) {
                return 0;
            }
            n = n->c[num];
        }
        return n->cnt;
    }
};

int main() {
    int rws, cls;
    cin >> rws >> cls;
    vector<vector<long long>> mtrx(rws, vector<long long>(cls));

    for (int i = 0; i < rws; i++) {
        for (int j = 0; j < cls; j++) {
            cin >> mtrx[i][j];
        }
    }

    Trie trie;
    for (const auto& lst : mtrx) {
        trie.ins(lst);
    }

    int qCnt;
    cin >> qCnt;
    vector<vector<long long>> qrs(qCnt);

    for (int i = 0; i < qCnt; i++) {
        while (true) {
            long long num;
            cin >> num;
            if (num == -1) break;
            qrs[i].push_back(num);
        }
    }

    for (const auto& qr : qrs) {
        cout << trie.cntPref(qr) << endl;
    }

    return 0;
}

//Siemens The Bot and the Game