小Gが住む都市は、$N$ 個の頂点と $M$ 本の辺からなる有向グラフとして抽象化できます。都市の建設過程において、道路にはいくつかの変化が生じます。具体的には、合計 $Q$ 回の操作が行われ、操作は以下の2種類です。
- 頂点 $p$ と $tot$ 個の整数 $a_i$ が与えられ、グラフに $a_i$ から $p$ への辺を追加する。
- 頂点 $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$ はビット単位の排他的論理和（XOR）を表します。初期状態のグラフおよび各操作後のグラフには、多重辺や自己ループは存在しないことが保証されます。また、辺を削除する際、その辺は必ずグラフ上に存在します。また、強制オンラインにするための手段がいくつか用意されています。
入力
- 1行目に、現在のテストケースの番号を表す整数 $ID$ が与えられます（サンプルの $ID$ はすべて 0 です）。
- 2行目に、強制オンラインかどうかを表す整数 $flag$ が与えられます（$0$ または $1$）。$flag=1$ の場合、このデータセットは強制オンラインを要求します。
- 3行目に、グラフの頂点数 $N$、初期の辺数 $M$、操作回数 $Q$ を表す3つの整数が与えられます。
- 4行目に、各頂点の重み $val_i$ を表す $N$ 個の非負整数が与えられます。
- 続く $M$ 行には、初期グラフの $u$ から $v$ への有向辺を表す2つの整数 $u, v$ が与えられます。
続く $2Q$ 行には、各操作が2行ずつ記述されます。
- 1行目に $k, p, tot$ が与えられます。$k$ は $0$ または $1$ で、$0$ の場合は辺の追加、$1$ の場合は辺の削除を表します。
- 2行目に 互いに異なる $tot$ 個の整数 $a_i$ が与えられます。
$flag = 1$（強制オンライン）の場合、$lastAns$ を前回の操作後の出力結果（最初の操作時は $lastAns=0$）とし、$p$ に $lastAns$ を XOR した値を真の $p$ として扱います。
注意：$lastAns$ は非常に大きな値になる可能性があります！
出力
$Q$ 行にわたり、各操作後の答えを整数で出力してください。
入出力例
入出力例 1
入力 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
入力 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
入力 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
注記
これら3つのサンプルは、それぞれタイプ1、タイプ2、タイプ3の要件を満たしています。
制約
本問題は合計20個のテストケースで構成され、各ケースは5点です。 すべてのテストケースは以下の3つのタイプに分類されます。
タイプ1（合計20点）
$Q = 1$、$tot = 0$ が保証され、初期グラフに対する答えを求めるのみです。 また、$0 \le val_i \le 1$ です。
| $ID$ | $flag$ | $N$ | $M$ | $Q$ | $tot$ |
|---|---|---|---|---|---|
| 1 | 0 | $\le 35000$ | $\le 100000$ | 1 | 0 |
| 2 | 0 | $\le 35000$ | $\le 100000$ | 1 | 0 |
| 3 | 0 | $\le 35000$ | $\le 100000$ | 1 | 0 |
| 4 | 0 | $\le 35000$ | $\le 100000$ | 1 | 0 |
タイプ2（合計40点）
辺の削除操作が存在しないことが保証されます（すべての操作で $k = 0$）。また、$tot = 1$、$M = 0$ です。
| $ID$ | $flag$ | $N$ | $M$ | $Q$ | $tot$ |
|---|---|---|---|---|---|
| 5 | 0 | $\le 500$ | 0 | $\le 15000$ | 1 |
| 6 | 0 | $\le 600$ | 0 | $\le 20000$ | 1 |
| 7 | 0 | $\le 800$ | 0 | $\le 30000$ | 1 |
| 8 | 0 | $\le 1000$ | 0 | $\le 50000$ | 1 |
| 9 | 0 | $\le 1500$ | 0 | $\le 80000$ | 1 |
| 10 | 0 | $\le 2000$ | 0 | $\le 100000$ | 1 |
| 11 | 1 | $\le 2500$ | 0 | $\le 150000$ | 1 |
| 12 | 1 | $\le 2500$ | 0 | $\le 150000$ | 1 |
タイプ3（合計40点）
特別な制約はありません。
| $ID$ | $flag$ | $N$ | $M$ | $Q$ | $tot$ |
|---|---|---|---|---|---|
| 13 | 0 | $\le 10$ | / | $\le 10$ | / |
| 14 | 0 | $\le 50$ | / | $\le 50$ | / |
| 15 | 0 | $\le 200$ | / | $\le 200$ | / |
| 16 | 0 | $\le 300$ | / | $\le 300$ | / |
| 17 | 0 | $\le 400$ | / | $\le 800$ | / |
| 18 | 0 | $\le 400$ | / | $\le 800$ | / |
| 19 | 0 | $\le 400$ | / | $\le 800$ | / |
| 20 | 1 | $\le 400$ | / | $\le 800$ | / |
すべてのデータにおいて以下が保証されます：
- $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$
時間とメモリの制限
不可抗力により、タイプごとに制限時間が異なります。
- タイプ1：2秒
- タイプ2：1秒
- タイプ3：1.5秒
メモリ制限：512 MB