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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <inttypes.h>
#include <vector>
#include <iostream>
#include <set>

typedef uint_fast16_t Element;

Element zasieg;

class Zbior {
public:
    virtual bool nalezy(Element) const = 0;
    virtual Element rozmiar() const = 0;
    // void wypisz() {
    //     std::cerr << "{";
    //     for (Element i=1; i <= zasieg; ++i) {
    //         if (this->nalezy(i)) {
    //             std::cerr << i << ", ";
    //         }
    //     }
    //     std::cerr << "}" << std::endl;
    // }
};

class Wielokrotnosci : public Zbior {
    Element dzielnik;
public:
    Wielokrotnosci(Element dzielnik) : dzielnik(dzielnik) {}
    bool nalezy(Element e) const override {
        return e % dzielnik == 0;
    }
    Element rozmiar() const override {
        return zasieg / dzielnik;
    }
};

class Suma : public Zbior {
    const Zbior *za;
    const Zbior *zb;
public:
    Suma(const Zbior *za, const Zbior *zb) : za(za), zb(zb) {}
    bool nalezy(Element e) const override {
        return za->nalezy(e) || zb->nalezy(e);
    }
    Element rozmiar() const override {
        auto ra = za->rozmiar();
        auto rb = zb->rozmiar();
        return ra + rb - ra*rb/zasieg;
    }
};

class Przeciecie : public Zbior {
    const Zbior *za;
    const Zbior *zb;
public:
    Przeciecie(const Zbior *za, const Zbior *zb) : za(za), zb(zb) {}
    bool nalezy(Element e) const override {
        return za->nalezy(e) && zb->nalezy(e);
    }
    Element rozmiar() const override {
        auto ra = za->rozmiar();
        auto rb = zb->rozmiar();
        return ra*rb/zasieg;
    }
};

class Dopelnienie : public Zbior {
    const Zbior *za;
public:
    Dopelnienie(const Zbior *za) : za(za) {}
    bool nalezy(Element e) const override {
        return !za->nalezy(e);
    }
    Element rozmiar() const override {
        auto ra = za->rozmiar();
        return zasieg - ra;
    }
};


class Wymieniony : public Zbior {
    std::set<Element> elementy;
    bool wprost;
public:
    Wymieniony(const Zbior *za, bool wprost=true) : wprost(wprost) {
        for (Element i=1; i <= zasieg; ++i) {
            if (za->nalezy(i) == wprost) {
                elementy.insert(i);
            }
        }
    }
    bool nalezy(Element e) const override {
        if (wprost) {
            return elementy.contains(e);
        }
        return !elementy.contains(e);
    }
    Element rozmiar() const override {
        if (wprost) {
            return elementy.size();
        }
        return zasieg - elementy.size();
    }
};


int main() {
    Element n;
    int m;
    int q;
    int op;
    int za;
    int zb;
    int x;
    int v;

    std::cin >> n >> m >> q;
    zasieg = n;

    std::vector<Zbior*> zbiory;
    zbiory.reserve(1+n+m);
    zbiory.push_back(new Wielokrotnosci(n+1));
    for (int i = 1; i <= n; ++i) {
        zbiory.push_back(new Wielokrotnosci(i));
        // zbiory[i]->wypisz();
    }
    for (int i = n+1; i <= n+m; ++i) {
        std::cin >> op >> za;
        if (op == 1) {
            std::cin >> zb;
            zbiory.push_back(new Suma(zbiory[za], zbiory[zb]));
        }
        else if (op == 2) {
            std::cin >> zb;
            zbiory.push_back(new Przeciecie(zbiory[za], zbiory[zb]));
        }
        else {
            zbiory.push_back(new Dopelnienie(zbiory[za]));
        }
        if (zbiory[i]->rozmiar() < 30) {
            zbiory[i] = new Wymieniony(zbiory[i]);
        }
        else if (zasieg - zbiory[i]->rozmiar() < 30) {
            zbiory[i] = new Wymieniony(zbiory[i], false);
        }
        // zbiory[i]->wypisz();
    }
    for (int i = 1; i <= q; ++i) {
        std::cin >> x >> v;
        std::cout << (zbiory[x]->nalezy(v) ? "TAK" : "NIE") << std::endl;
    }
}