OIG XIV - sam

// https://szkopul.edu.pl/problemset/problem/_2d84Hdvu-G-juPaRQvUAeZD/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 2 * 1000 * 1001;
constexpr int INF = 1000 * 1000 * 1001;

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

typedef vec<vec<int>> _kra;

int conv(const std::vector<int>& a) {
    int r = 0;
    for (const auto& b : a) {
        r |= (1 << (b - 1));
    }
    return r;
}

std::string getBinaryString(int a, int k) {
    return std::bitset<64>(a).to_string().substr(64 - k);
}

int c[sizik], d[sizik];
std::pair<int, int> dp[sizik];

void solve() {
    int n, k, q;
    std::cin >> n >> k >> q;

    std::vector<int> m;
    for (int i = 0; i < (1 << k); i++) {
        m.push_back(i);
        c[i] = INF;
        d[i] = INF;
    }

    for (int i = 1; i <= n; i++) {
        int y, p;
        std::cin >> y >> p;

        std::vector<int> z;
        for (int j = 0; j < p; j++) {
            int w;
            std::cin >> w;

            z.push_back(w);
        }

        int u = conv(z);
        if (c[u] > y) {
            c[u] = y;
            d[u] = i;
        }
    }

    std::sort(m.begin(), m.end(), [](int a, int b) { return __builtin_popcount(a) > __builtin_popcount(b); });

    for (const auto& a : m) {
        dp[a] = {c[a], d[a]};
        for (int i = 0; i < k; i++) {
            dp[a] = std::min(dp[a], dp[a | (1 << i)]);
        }
    }

    //...

    for (int i = 0; i < q; i++) {
        int p;
        std::cin >> p;

        std::vector<int> z;
        for (int j = 0; j < p; j++) {
            int w;
            std::cin >> w;

            z.push_back(w);
        }

        int u = conv(z);
        if (dp[u].first == INF) {
            std::cout << "NIE\n";
        } else {
            std::cout << dp[u].second << '\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;
}