小 G 所居住的城市可以抽象為一張 $N$ 個點 $M$ 條邊的 有向圖。在城市建設的過程中，該城市的道路會發生一些變化；具體來說，一共會有 $Q$ 次操作，包含以下兩種類型：

1. 給出點 $p$，再給出 $tot$ 個數 $a_i$，在圖中加入 $a_i$ 到 $p$ 的邊。
2. 給出點 $p$，再給出 $tot$ 個數 $a_i$，在圖中刪除 $a_i$ 到 $p$ 的邊。

好奇的小 G 想在每次操作後知道，所有點對之間的 可達情況。

令 $F(u, v)$ 表示 $u, v$ 之間的可達狀態，如果圖中存在一條從 $u$ 到 $v$ 的路徑，那麼 $F(u,v)= 1$，否則 $F(u,v)= 0$。容易發現 $F(u, v)$ 和 $F(v, u)$ 不一定相等，且 $F(u,u)$ 必然是 1。

為了方便詢問，每一個點有點權 $val_i$，你需要在每次操作後回答下式的值：

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

其中 $\oplus$ 表示兩個數的異或值。保證初始給出的圖以及每次操作後的圖 不存在重邊和自環；並且刪除一條邊時，圖上必然存在這條邊。我們還會有一些手段來 強制在線。

輸入格式

• 第一行包含一個整數 $ID$，表示當前是第 $ID$ 組測試資料；其中範例的 $ID$ 均為 0。
• 第二行包含一個整數 $flag$，保證 $flag$ 是 $0$ 或 $1$；當 $flag=1$ 時，這組資料要求強制在線。
• 第三行包含三個整數 $N, M, Q$，分別表示圖的點數、初始圖的邊數、需要進行的操作次數。
• 第四行包含 $N$ 個非負整數，表示每個點的點權 $val_i$。
• 接下來 $M$ 行，每行包含兩個整數 $u, v$，表示初始圖上有一條從 $u$ 到 $v$ 的有向邊。

• 接下來 $2Q$ 行，每兩行描述一次操作：

  • 第一行包含三個整數 $k, p, tot$。其中 $k$ 為 $0$ 或 $1$，當 $k=0$ 時，為加邊操作；反之為刪邊操作。
  • 第二行包含 $tot$ 個 互不相同 的整數 $a_i$。

當 $flag = 1$（即強制在線）時，令 $lastAns$ 表示上一次操作後輸出的答案（第一次操作的 $lastAns=0$），需要將 $p$ 異或上 $lastAns$ 作為 $p$ 的真實的值。

注意：$lastAns$ 可能會很大！

輸出格式

共 $Q$ 行，每行一個整數，表示這次操作後的答案。

範例

範例輸入 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

範例輸出 1

10

範例輸入 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

範例輸出 2

1067190165
2043082587
2961479386
4033244915
4438519384
8158342623
8158342623
12528106804
12528106804
12528106804

範例輸入 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

範例輸出 3

5862031096
4844805513
4844805513
2982371382
3999596965

說明

這三個範例分別滿足類型一、類型二、類型三的要求。

資料範圍

本題共 $20$ 個測試資料，每個測試資料的分值為 $5$ 分。 所有測試資料可分為以下三種類型：

類型一（共 20 分）

保證 $Q = 1$，$tot = 0$，即只需對原圖詢問答案。 且 $0 \le val_i \le 1$

類型二（共 40 分）

保證不存在刪邊操作，即每次操作 $k = 0$；同時 $tot = 1$，$M = 0$

類型三（共 40 分）

無特殊約定：

保證 $100\%$ 的資料滿足：

• $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$