33815번 - 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.