Dany jest graf nieskierowany składający się z $n$ wierzchołków i $m$ krawędzi. Wierzchołki są ponumerowane od zera: $0, 1, \dots, n - 1$. Twoim zadaniem jest przetworzenie $q$ zapytań. Każde zapytanie podaje parę $(u, v)$ i prosi o usunięcie krawędzi $(u, v)$ z grafu. Jeśli takiej krawędzi nie ma w grafie (na przykład gdy $u = v$), nie rób nic. Po każdym zapytaniu wypisz, czy graf jest spójny, czy nie.
Wejście
Wejście zawiera wiele przypadków testowych. Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 5 \cdot 10^5$), oznaczającą liczbę przypadków testowych. Następnie podane są opisy kolejnych przypadków testowych.
Pierwszy wiersz każdego przypadku testowego zawiera trzy liczby całkowite $n$, $m$ oraz $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): odpowiednio liczbę wierzchołków, krawędzi oraz zapytań.
Każdy z kolejnych $m$ wierszy zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($0 \le u_i, v_i < n$), reprezentujące krawędź między $u_i$ a $v_i$. W grafie nie ma pętli ani krawędzi wielokrotnych.
Każdy z kolejnych $q$ wierszy opisuje zapytanie. Parametry zapytania $u_j$ oraz $v_j$ nie są jednak podane bezpośrednio. Zamiast tego $j$-ty z tych wierszy zawiera dwie liczby całkowite $a_j$ oraz $b_j$ ($0 \le a_j, b_j < n$). Załóżmy, że odpowiedzią na $k$-te zapytanie jest $c_k = 1$, jeśli graf jest spójny, lub $c_k = 0$ w przeciwnym razie. Wówczas $u_j$ oraz $v_j$ są generowane według wzorów:
$$u_j = (2^{j-2}c_1 + 2^{j-3}c_2 + \dots + 2^1 c_{j-2} + 2^0 c_{j-1} + a_j) \bmod n,$$
$$v_j = (3^{j-2}c_1 + 3^{j-3}c_2 + \dots + 3^1 c_{j-2} + 3^0 c_{j-1} + b_j) \bmod n.$$
Suma wszystkich $n$, suma wszystkich $m$ oraz suma wszystkich $q$ po wszystkich przypadkach testowych nie przekraczają $10^6$.
Wyjście
Dla każdego przypadku testowego wypisz $q$ wierszy z liczbami całkowitymi $c_1, \dots, c_q$: odpowiedziami na kolejne zapytania.
Przykład
Przykładowe wejście 1
2 3 1 2 0 1 0 0 0 1 4 4 4 0 1 1 2 2 3 0 3 0 1 1 3 0 0 2 3
Przykładowe wyjście 1
0 0 1 1 0 0
Uwaga
W pierwszym przypadku testowym zapytania proszą o usunięcie krawędzi $(0, 0)$ (nie istnieje) oraz $(0, 1)$.
W drugim przypadku testowym zapytania proszą o usunięcie krawędzi $(0, 1)$, $(2, 0)$ (nie istnieje), $(3, 0)$ oraz $(0, 3)$ (została już usunięta przez poprzednią operację).