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
import sys
import numpy as np  # NumPy importowany – przydatny, gdybyśmy chcieli wykonywać operacje wektorowe

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    q = int(next(it))
    
    # Precompute tablica "base" – base[j] = 1 << j dla 0 <= j < n
    base = [0] * n
    base[0] = 1
    for j in range(1, n):
        base[j] = base[j - 1] << 1

    total = n + m  # liczba wszystkich zbiorów (indeksujemy od 1)
    sets = [0] * (total + 1)
    
    # Inicjalizacja zbiorów początkowych A1...An:
    # Dla i=1,...,n: A_i = {j : j mod i == 0} – czyli ustawiamy bity dla pozycji j-1, gdzie j jest wielokrotnością i.
    for i in range(1, n + 1):
        s = 0
        # indeksy: j = i, 2*i, 3*i, ... <= n; odpowiadają bity o indeksach j-1
        for j in range(i - 1, n, i):
            s |= base[j]
        sets[i] = s

    # Maska zawierająca bity [0, n-1] ustawione na 1
    mask = (1 << n) - 1

    # Przetwarzamy m operacji – dla operacji nowe zbiory mają indeksy n+1, n+2, ... n+m
    for i in range(1, m + 1):
        op = next(it)  # op jest typu bytes (np. b'1', b'2', b'3')
        idx = n + i
        if op == b'1':  # suma
            x = int(next(it))
            y = int(next(it))
            sets[idx] = sets[x] | sets[y]
        elif op == b'2':  # przecięcie
            x = int(next(it))
            y = int(next(it))
            sets[idx] = sets[x] & sets[y]
        elif op == b'3':  # negacja
            x = int(next(it))
            sets[idx] = mask ^ sets[x]
    
    # Odpowiadamy na q zapytań
    out_lines = []
    for _ in range(q):
        x = int(next(it))
        v = int(next(it))
        # Sprawdzamy, czy bit (v-1) jest ustawiony:
        if (sets[x] >> (v - 1)) & 1:
            out_lines.append("TAK")
        else:
            out_lines.append("NIE")
    
    sys.stdout.write("\n".join(out_lines))
    
if __name__ == '__main__':
    main()