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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#ifdef _WIN32
#include <io.h>
#include <fcntl.h>
#endif

#include <assert.h>
#include <iostream>
#include <stdint.h>

#include <bitset>

typedef int64_t i64;
typedef uint64_t u64;

typedef u64 word;

const i64 MaxN = 50000;
const i64 MaxM = 400000;
const i64 MaxQ = 1000000;
const i64 MaxNm = MaxN + MaxM;

const i64 MaxWc = 782;
const i64 MaxBmSize = MaxNm * MaxWc;

word* Bm;
i64 N;
i64 M;
i64 Wc;
i64 WordAddrShift = 6;
u64 WordAddrMask = (1 << WordAddrShift) - 1;

void Init(u64 n)
{
    Bm = new word[MaxBmSize];
    assert(Bm != nullptr);

    N = n;
    M = 0;
    Wc = (n >> WordAddrShift) + ((n & WordAddrMask) != 0 ? 1 : 0);
    std::cerr << Wc << std::endl;

    word* Zbior = Bm;
    for (i64 i = 0; i < N; i++) {
        for (i64 j = 0; j < Wc; j++) Zbior[j] = 0;
        i64 wartosc = i + 1;
        i64 bitaddr = wartosc - 1;
        while (bitaddr < N) {
            Zbior[bitaddr >> WordAddrShift] |= (u64)1 << (bitaddr & WordAddrMask);
            bitaddr += wartosc;
        }
        /*
        for (i64 j = 0; j < Wc; j++) std::cerr << std::bitset<64>(Zbior[j]) << " ";
        std::cerr << std::endl;
        */
        Zbior += Wc;
    }
}

void AddOper(u64 oper, u64 par1, u64 par2)
{
    M++;
    word* Wynik = Bm + Wc*(N + M - 1);
    word* ZbX = Bm + Wc*(par1 - 1);
    if (oper == 1) {
        word* ZbY = Bm + Wc*(par2 - 1);
        for (i64 i = 0; i < Wc; i++) {
            Wynik[i] = ZbX[i] | ZbY[i];
        }
    } else if (oper == 2) {
        word* ZbY = Bm + Wc*(par2 - 1);
        for (i64 i = 0; i < Wc; i++) {
            Wynik[i] = ZbX[i] & ZbY[i];
        }
    } else {
        for (i64 i = 0; i < Wc; i++) {
            Wynik[i] = ~ZbX[i];
        }
    }
}

bool Check(u64 zb, u64 wartosc)
{
    word* Zbior = Bm + Wc*(zb - 1);
    i64 bitaddr = wartosc - 1;
    return Zbior[bitaddr >> WordAddrShift] & ((u64)1 << (bitaddr & WordAddrMask));
}

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

#ifdef _WIN32
    _setmode( _fileno( stdout ),  _O_BINARY );
#endif

    i64 n, m, q;
    std::cin >> n >> m >> q;
    assert(1 <= n);
    assert(n <= MaxN);
    assert(1 <= m);
    assert(m <= MaxM);
    assert(1 <= q);
    assert(q <= MaxQ);

    Init(n);
    for (i64 i = 0; i < m; i++) {
        i64 oper, par1;
        i64 par2 = 0;
        std::cin >> oper >> par1;
        assert(oper == 1 || oper == 2 || oper == 3);
        assert(1 <= par1);
        assert(par1 <= n + i);
        if (oper != 3) {
            std::cin >> par2;
            assert(1 <= par2);
            assert(par2 <= n + i);
        }
        AddOper(oper, par1, par2);
    }
    

    for (i64 i = 0; i < q; i++) {
        i64 zb, wartosc;
        std::cin >> zb >> wartosc;
        assert(1 <= zb);
        assert(zb <= n + m);
        assert(1 <= wartosc);
        assert(wartosc <= n);
        auto b = Check(zb, wartosc);
        std::cout << (b ? "TAK\n" : "NIE\n");
    }

    std::cout.flush();

    return 0;
}