1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<int> op_type(m), op_x(m), op_y(m, 0);
    for (int i = 0; i < m; i++) {
        cin >> op_type[i] >> op_x[i];
        op_x[i]--;  // 0-indexed
        if (op_type[i] != 3) {
            cin >> op_y[i];
            op_y[i]--;  // 0-indexed
        }
    }

    vector<int> qx(q), qv(q);
    for (int i = 0; i < q; i++) {
        cin >> qx[i] >> qv[i];
        qx[i]--;  // 0-indexed
    }

    // Group queries by their v value
    vector<vector<int>> queries_for_v(n + 1);
    for (int i = 0; i < q; i++) {
        queries_for_v[qv[i]].push_back(i);
    }

    // Collect distinct v-values that appear in queries (in order 1..n)
    vector<int> distinct_v;
    for (int v = 1; v <= n; v++) {
        if (!queries_for_v[v].empty()) {
            distinct_v.push_back(v);
        }
    }

    vector<bool> ans(q, false);

    int total = n + m;
    vector<uint64_t> mask(total);

    int dv = (int)distinct_v.size();
    for (int bs = 0; bs < dv; bs += 64) {
        int be = min(bs + 64, dv);
        int bsize = be - bs;
        uint64_t full_mask = (bsize == 64) ? ~0ULL : ((1ULL << bsize) - 1ULL);

        // Clear base set masks (A_1..A_n)
        fill(mask.begin(), mask.begin() + n, 0ULL);

        // For each v_k in batch, enumerate divisors d of v_k.
        // Bit k of mask[d-1] means v_k ∈ A_d (i.e., d divides v_k).
        for (int k = 0; k < bsize; k++) {
            int v = distinct_v[bs + k];
            for (int d = 1; d * d <= v; d++) {
                if (v % d == 0) {
                    if (d <= n) mask[d - 1] |= (1ULL << k);
                    int d2 = v / d;
                    if (d2 != d && d2 <= n) mask[d2 - 1] |= (1ULL << k);
                }
            }
        }

        // Evaluate all m operations in order
        for (int i = 0; i < m; i++) {
            int idx = n + i;
            if (op_type[i] == 1) {
                mask[idx] = mask[op_x[i]] | mask[op_y[i]];
            } else if (op_type[i] == 2) {
                mask[idx] = mask[op_x[i]] & mask[op_y[i]];
            } else {
                mask[idx] = (~mask[op_x[i]]) & full_mask;
            }
        }

        // Answer queries for this batch
        for (int k = 0; k < bsize; k++) {
            int v = distinct_v[bs + k];
            for (int qi : queries_for_v[v]) {
                ans[qi] = (mask[qx[qi]] >> k) & 1ULL;
            }
        }
    }

    // Output all answers
    for (int i = 0; i < q; i++) {
        cout << (ans[i] ? "TAK" : "NIE") << '\n';
    }

    return 0;
}