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
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <cassert>

#include <array>

static const size_t MAX_N = 50 * 1000;
static const size_t MAX_M = 400 * 1000;
static const size_t MAX_Q = 1000 * 1000;

using block_t = std::array<uint64_t, (MAX_N + 63) / 64>;

block_t* blocks;

void init_base_block(size_t bid) {
    block_t& b = blocks[bid];
    for (size_t i = 0; i < b.size(); i++) {
        b[i] = 0;
    }
    for (size_t i = 0; i < b.size() * 64; i += bid) {
        b[i / 64ULL] |= 1ULL << (i % 64);
    }
}

void sum_blocks(size_t a_id, size_t b_id, size_t dest_id) {
    const auto& a = blocks[a_id];
    const auto& b = blocks[b_id];
    auto& dest = blocks[dest_id];
    for (size_t i = 0; i < dest.size(); i++) {
        dest[i] = a[i] | b[i];
    }
}

void mul_blocks(size_t a_id, size_t b_id, size_t dest_id) {
    const auto& a = blocks[a_id];
    const auto& b = blocks[b_id];
    auto& dest = blocks[dest_id];
    for (size_t i = 0; i < dest.size(); i++) {
        dest[i] = a[i] & b[i];
    }
}

void neg_block(size_t source_id, size_t dest_id) {
    const auto& source = blocks[source_id];
    auto& dest = blocks[dest_id];
    for (size_t i = 0; i < dest.size(); i++) {
        dest[i] = ~source[i];
    }
}

int main(int argc, char** argv) {
    int n, m, q;
    scanf("%i %i %i", &n, &m, &q);

    blocks = new block_t[n + m + 1];

    for (int i = 1; i <= n; i++) {
        init_base_block(i);
    }

    for (int i = 1; i <= m; i++) {
        int op, arg1, arg2;
        scanf("%i", &op);
        switch (op) {
        case 1:
            scanf("%i %i", &arg1, &arg2);
            sum_blocks(arg1, arg2, n + i);
            break;
        case 2:
            scanf("%i %i", &arg1, &arg2);
            mul_blocks(arg1, arg2, n + i);
            break;
        case 3:
            scanf("%i", &arg1);
            neg_block(arg1, n + i);
            break;
        default:
            assert(false);
        }
    }

    for (int i = 1; i <= q; i++) {
        int x, v;
        scanf("%i %i", &x, &v);
        puts((blocks[x][v / 64] & (1ULL << (v % 64))) ? "TAK" : "NIE");
    }

    delete[] blocks;

    return 0;
}