Miasto, w którym mieszka małe G, można przedstawić jako skierowany graf o $N$ wierzchołkach i $M$ krawędziach. W trakcie rozbudowy miasta drogi ulegają zmianom. Dokładniej, przewidziano $Q$ operacji dwóch typów:

1. Podano wierzchołek $p$ oraz $tot$ liczb $a_i$. Należy dodać do grafu krawędzie z $a_i$ do $p$.
2. Podano wierzchołek $p$ oraz $tot$ liczb $a_i$. Należy usunąć z grafu krawędzie z $a_i$ do $p$.

Ciekawe świata małe G chce po każdej operacji poznać stan osiągalności między wszystkimi parami wierzchołków.

Niech $F(u, v)$ oznacza stan osiągalności między $u$ a $v$. Jeśli w grafie istnieje ścieżka z $u$ do $v$, to $F(u, v) = 1$, w przeciwnym razie $F(u, v) = 0$. Łatwo zauważyć, że $F(u, v)$ nie musi być równe $F(v, u)$, a $F(u, u)$ zawsze wynosi 1.

Dla ułatwienia zapytań, każdy wierzchołek posiada wagę $val_i$. Po każdej operacji należy obliczyć wartość poniższego wyrażenia:

$$ \sum_{u=1}^{N} \sum_{v=1}^{N} F(u, v) \times (val_u \oplus val_v) $$

gdzie $\oplus$ oznacza operację XOR. Gwarantuje się, że graf początkowy oraz graf po każdej operacji nie zawiera krawędzi wielokrotnych ani pętli własnych, a przy usuwaniu krawędzi gwarantuje się, że dana krawędź istnieje w grafie. Zastosujemy również mechanizmy wymuszające tryb online.

Wejście

• Pierwsza linia zawiera liczbę całkowitą $ID$, oznaczającą numer zestawu danych testowych; dla przykładów $ID$ wynosi 0.
• Druga linia zawiera liczbę całkowitą $flag$, która wynosi $0$ lub $1$. Jeśli $flag=1$, zestaw danych wymaga odpowiedzi w trybie online.
• Trzecia linia zawiera trzy liczby całkowite $N, M, Q$, oznaczające odpowiednio liczbę wierzchołków, liczbę krawędzi w grafie początkowym oraz liczbę operacji.
• Czwarta linia zawiera $N$ nieujemnych liczb całkowitych, oznaczających wagi wierzchołków $val_i$.
• Następne $M$ linii zawiera po dwie liczby całkowite $u, v$, oznaczające istnienie skierowanej krawędzi z $u$ do $v$ w grafie początkowym.
• Następne $2Q$ linii opisuje operacje, każda zajmuje dwie linie:
  • Pierwsza linia zawiera trzy liczby całkowite $k, p, tot$. Jeśli $k=0$, operacja polega na dodaniu krawędzi; w przeciwnym razie na usunięciu krawędzi.
  • Druga linia zawiera $tot$ parami różnych liczb całkowitych $a_i$.

Jeśli $flag = 1$ (tryb online), niech $lastAns$ oznacza odpowiedź na poprzednią operację (dla pierwszej operacji $lastAns=0$). Wartość $p$ należy zaktualizować poprzez wykonanie operacji XOR z $lastAns$, aby uzyskać rzeczywistą wartość $p$.

Uwaga: $lastAns$ może być bardzo dużą liczbą!

Wyjście

$Q$ linii, każda zawierająca jedną liczbę całkowitą będącą odpowiedzią po danej operacji.

Przykład

Przykład 1

0
0
10 10 1
0 1 1 1 1 1 1 1 1 0
1 7
2 1
7 3
3 7
10 2
8 5
2 10
2 5
3 6
4 5
0 1 0

Wyjście 1

10

Przykład 2

0
0
5 0 10
775753708 730589119 295766137 411078803 10973174
0 1 1
3
0 2 1
3
0 1 1
4
0 3 1
2
0 5 1
4
0 4 1
1
0 1 1
2
0 2 1
5
0 4 1
3
0 1 1
5

Wyjście 2

1067190165
2043082587
2961479386
4033244915
4438519384
8158342623
8158342623
12528106804
12528106804
12528106804

Przykład 3

0
0
5 7 5
505212782 768758516 141501571 189544889 292811675
2 1
2 3
2 5
3 1
3 4
4 1
5 3
0 3 2
1 4
1 5 1
2
0 1 1
5
1 1 4
2 3 4 5
0 5 1
2

Wyjście 3

5862031096
4844805513
4844805513
2982371382
3999596965

Uwagi

Trzy powyższe przykłady odpowiadają odpowiednio typom pierwszym, drugim i trzecim.

Ograniczenia

Zadanie składa się z 20 zestawów danych, każdy wart 5 punktów. Wszystkie zestawy dzielą się na trzy typy:

Typ 1 (łącznie 20 punktów)

Gwarantowane $Q = 1$, $tot = 0$, czyli wymagane jest jedynie zapytanie o odpowiedź dla grafu początkowego. Ponadto $0 \le val_i \le 1$.

Typ 2 (łącznie 40 punktów)

Gwarantowany brak operacji usuwania krawędzi, czyli w każdej operacji $k = 0$. Ponadto $tot = 1$, $M = 0$.

Typ 3 (łącznie 40 punktów)

Brak dodatkowych założeń:

Gwarantuje się, że 100% danych spełnia:

• $N \ge 2$
• $0 \le M \le N(N-1)$
• $1 \le u, v, p, a_i \le N$
• $0 \le tot < N$
• $0 \le val_i \le 10^9$

Limity czasu i pamięci

Ze względu na specyfikę zadania, limity czasu różnią się w zależności od typu:

• Typ 1: 2 sekundy
• Typ 2: 1 sekunda
• Typ 3: 1,5 sekundy

Limit pamięci: 512 MB