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
#include <cstdio>
#include <cstdint>
#include <vector>
#include <map>
using namespace std;

const int MAXNM = 450002;
uint64_t S[MAXNM];

int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);

    vector<int> ot(m), ox(m), oy(m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &ot[i], &ox[i]);
        if (ot[i] != 3) scanf("%d", &oy[i]);
    }

    vector<int> qx(q), qv(q);
    for (int i = 0; i < q; i++)
        scanf("%d %d", &qx[i], &qv[i]);

    // Grupuj zapytania wg bloków 64-bitowych
    int nblocks = (n + 63) / 64;
    vector<vector<int>> bq(nblocks);
    for (int i = 0; i < q; i++)
        bq[(qv[i] - 1) / 64].push_back(i);

    vector<char> ans(q);

    for (int b = 0; b < nblocks; b++) {
        if (bq[b].empty()) continue;
        int lo = b * 64 + 1;
        int hi = min(lo + 63, n);
        uint64_t mask = (hi - lo + 1 == 64) ? ~0ULL : ((1ULL << (hi - lo + 1)) - 1);

        // Inicjalizacja zbiorów bazowych A_1..A_n
        for (int j = 1; j <= n; j++) {
            S[j] = 0;
            int f = ((lo + j - 1) / j) * j; // najmniejsza wielokrotność j >= lo
            for (int k = f; k <= hi; k += j)
                S[j] |= 1ULL << (k - lo);
        }

        // Przetwarzanie operacji
        for (int i = 0; i < m; i++) {
            int idx = n + 1 + i;
            if (ot[i] == 1)      S[idx] = S[ox[i]] | S[oy[i]];
            else if (ot[i] == 2) S[idx] = S[ox[i]] & S[oy[i]];
            else                 S[idx] = ~S[ox[i]] & mask;
        }


        for (int qi : bq[b])
            ans[qi] = (S[qx[qi]] >> (qv[qi] - lo)) & 1;
    }

    for (int i = 0; i < q; i++)
        puts(ans[i] ? "TAK" : "NIE");
}