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
#include <bits/stdc++.h>
using namespace std;

const int P = 0, X = 1, Y = 2;
const int UNION = 1, INTERSECTION = 2, COMPLEMENT = 3;
const string TAK = "TAK", NIE = "NIE";
long long int n, m;
const int MAX_N = 50'001;
//const int MAX_N = 8;
vector<array<int, 3>> actions;
vector<bitset<MAX_N>> subsets;


int main() {
//	ifstream cin("tests/zb1_0.in");
//	ifstream cin("tests1/in/640.in");

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

//	cout << subsets.max_size() << endl;

	int q, p, x, v;
	cin >> n;
	cin >> m;
	cin >> q;

	actions.resize(m + 1);
	subsets.resize(n + m + 1);
//	vector<bitset<MAX_N>> subsets(n + m + 1);

	for (int i = 1; i <= m; i++) {
		cin >> p;
		actions[i][P] = p;
		cin >> actions[i][X];
		if (p != COMPLEMENT) {
			cin >> actions[i][Y];
		}
	}

	subsets[1].flip();
	for (int i = 2; i <= n; i++) {
		for (int p = i; p <= n; p += i) {
			subsets[i].set(p);
		}
	}

	for (int i = 1, s = n + 1; i <= m; i++, s++) {
		if (actions[i][P] == UNION) {
			subsets[s] = subsets[actions[i][X]] | subsets[actions[i][Y]];
		} else if (actions[i][P] == INTERSECTION) {
			subsets[s] = subsets[actions[i][X]] & subsets[actions[i][Y]];
		} else if (actions[i][P] == COMPLEMENT) {
			subsets[s] = ~subsets[actions[i][X]];
		}
	}

//	for (int i = 1; i <= n + m + 1; i++) {
//		cout << subsets[i] << endl;
//	}

	for (int i = 0; i < q; i++) {
		cin >> x;
		cin >> v;
		const bool contains = subsets[x][v];
		cout << (contains ? TAK : NIE) << endl;
	}

	return 0;
}