Zbiory 1

W tym zadaniu będziemy rozpatrywać ciąg $n + m$ podzbiorów zbioru $\{1, \dots , n\}$. Zbiory $A_1, \dots , A_n$ są zdefiniowane następująco: wartość $1 ≤ i ≤ n$ należy do zbioru $A_j$ wtedy i tylko wtedy, gdy $i$ jest podzielne przez $j$.

Przykładowo dla $n = 7$ kolejne zbiory są następujące:

• $A_1 = \{1, 2, 3, 4, 5, 6, 7\}$
• $A_2 = \{2, 4, 6\}$
• $A_3 = \{3, 6\}$
• $A_4 = \{4\}$
• $A_5 = \{5\}$
• $A_6 = \{6\}$
• $A_7 = \{7\}$

Kolejnych $m$ zbiorów – $A_{n+1}, A_{n+2}, \dots , A_{n+m}$ – powstaje przez operacje sum, przecięć lub negacji na poprzednich zbiorach.

• Operacja sumy zbiorów $A_i$ oraz $A_j$ (oznaczana przez $A_i ∪ A_j$) tworzy zbiór zawierający wszystkie liczby należące do któregokolwiek z $A_i$ lub $A_j$.
• Operacja przecięcia zbiorów $A_i$ oraz $A_j$ (oznaczana przez $A_i ∩ A_j$) tworzy zbiór zawierający wszystkie liczby należące do obu $A_i$ oraz $A_j$.
• Operacja negacji zbioru $A_i$ (oznaczana przez $A'_i$) tworzy zbiór zawierający wszystkie liczby całkowite $1 ≤ j ≤ n$, które nie należą do $A_i$.

Przykładowy ciąg operacji może wyglądać następująco:

• $A_8 = A_5 ∪ A_7 = \{5, 7\}$
• $A_9 = A_2 ∩ A_3 = \{6\}$
• $A_{10} = A'_8 = \{1, 2, 3, 4, 6\}$
• $A_{11} = A_{10} ∩ A_8 = \{\};$
• $A_{12} = A'_3 = \{1, 2, 4, 5, 7\}$
• $A_{13} = A_{12} ∪ A_{12} = \{1, 2, 4, 5, 7\}$
• $A_{14} = A_{10} ∩ A_{13} = \{1, 2, 4\}$
• $A_{15} = A_9 ∪ A_{14} = \{1, 2, 4, 6\}$

Mając dane $n$, $m$ oraz listę operacji tworzących zbiory, odpowiedz na $q$ zapytań postaci: czy dana liczba $v$ należy do danego zbioru $A_x$.

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite $n$, $m$, $q$ ($1 ≤ n ≤ 50\, 000$, $1 ≤ m ≤ 400\, 000$, $1 ≤ q ≤ 1\, 000\, 000$), oznaczające odpowiednio liczbę początkowych zbiorów, liczbę operacji oraz liczbę zapytań.

Kolejne $m$ wierszy zawierają opisy operacji. Wiersz numer $i$ opisujący w jaki sposób powstał zbiór $A_{n+i}$, jest w jednej z trzech postaci:

• 1 $x$ $y$ – oznaczającej operację sumy $A_{n+i} = A_x ∪ A_y$,
• 2 $x$ $y$ – oznaczającej operację przecięcia $A_{n+i} = A_x ∩ A_y$,
• 3 $x$ – oznaczającej operację negacji $A_{n+i} = A'_x$.

W każdej z tych postaci wartości $x$, $y$ spełniają warunek $1 ≤ x, y < n + i$, tzn. każda operacja odwołuje się tylko do poprzednich zbiorów.

Kolejne $q$ wierszy zawiera zapytania. Każdy z nich zawiera dwie liczby całkowite $x$ oraz $v$ ($1 ≤ x ≤ n + m$, $1 ≤ v ≤ n$), które oznaczają pytanie o to, czy $v ∈ A_x$.

Na wyjście należy wypisać $q$ wierszy zawierających odpowiedzi na kolejne zapytania. Każdy z wierszy ma zawierać jedno ze słów TAK lub NIE. Słowo TAK oznacza, że $v ∈ A_x$ dla odpowiednich $x$, $v$, zaś słowo NIE oznacza, że $v \not\in A_x$.

Wyjaśnienie przykładu: Test przykładowy odpowiada przykładowym operacjom opisanym w treści zadania.