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
#include <iostream>
#include <cstdio>
#include <cstdlib>

#define MAXN 50000
int n, m, q, s, x, y, z;

int c, i, j;
void SKIP_WHITESPACE() {
    while (1) {
        c = fgetc(stdin);
        if (c != ' ' && c != '\n' && c != '\r')
            break;
    }
}

int READ_INT() {
    SKIP_WHITESPACE();
    int ret = c - '0';
    while (1) {
        c = fgetc(stdin);
        if (c < '0' || c > '9')
            break;
        ret = ret * 10 + c - '0';
    }
    return ret;
}

uint64_t* t;

#define TSET(xi, bi)   t[xi * s + bi / 64] |= (1ULL << (bi % 64))
#define TCLR(xi, bi)   t[xi * s + bi / 64] &= ~(1ULL << (bi % 64))
#define TGET(xi, bi)   ((t[xi * s + bi / 64] >> (bi % 64)) & 1)
#define TSUM(ri, ai, bi, si) t[ri * s + si] = t[ai * s + si] | t[bi * s + si]
#define TMUL(ri, ai, bi, si) t[ri * s + si] = t[ai * s + si] & t[bi * s + si]
#define TNEG(ri, ai, si) t[ri * s + si] = ~t[ai * s + si]

void show() {
    int i, j, k;
    std::cout << "n=" << n << std::endl;
    std::cout << "m=" << m << std::endl;
    std::cout << "q=" << q << std::endl;
    for (i = 1; i <= n + m; ++i) {
        std::cout << "{" << i << "}:";
        for (j = 1; j <= n; ++j) {
            std::cout << TGET(i, j);
            if (j%8 == 0) std::cout<<" "; 
            if (j%64 == 0) std::cout<<"| "; 
        }
        std::cout << "\n";
    }
}

int main(int argc, char* argv[]) {
    std::ios_base::sync_with_stdio (false);

    n = READ_INT();
    m = READ_INT();
    q = READ_INT();

    s = n / 64 + 1;
    t = new uint64_t[(n + m + 2)*s];
    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= n; ++j) {
            if (j % i == 0) {
                TSET(i, j);
            } else {
                TCLR(i, j);
            }
        }

    }

    for (i = n + 1; i <= n + m; ++i) {
        x = READ_INT();
        if (x == 1) {
            y = READ_INT();
            z = READ_INT();

            for (j = 0; j < s; ++j) {
                TSUM(i, y, z, j);
            }
        }
        else if (x == 2) {
            y = READ_INT();
            z = READ_INT();

            for (j = 0; j < s; ++j) {
                TMUL(i, y, z, j);
            }
        }
        else if (x == 3) {
            y = READ_INT();

            for (j = 0; j < s; ++j) {
                TNEG(i, y, j);
            }
        }

    }

    for (i = 0; i < q; ++i) {
        x = READ_INT();
        y = READ_INT();
        std::cout << ((TGET(x,y) == 1) ? "TAK\n" : "NIE\n");
    }

//    show();
    return EXIT_SUCCESS;
}