/ 
実行時間制限: 8 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N 頂点 M 辺の連結無向グラフ G が与えられます。 i 番目の辺は 頂点 U_i と頂点 V_i を結ぶ、重み W_i、色 C_i の辺です。 G は自己ループを含みませんが、多重辺を含む場合もあります。
また、K 個の頂点対 (A_1, B_1), (A_2, B_2), \ldots, (A_K, B_K) が与えられます。
Q 個のクエリが順に与えられ、j 番目のクエリは、頂点 X_j と頂点 Y_j を結ぶ、重み Z_j、色 D_j の辺を追加するというものです。 この追加された辺には M+j 番目というインデックスが割り当てられます。
q=0, 1, \dots, Q について、q 番目までのクエリを処理した時点における、以下の問題の答えを求めてください。
G の最小重み全域木を T とする。 ただし、そのような全域木が複数ある場合は、重みが等しい辺同士ならインデックスが小さい辺を優先して使用する（すなわち、使用する辺のインデックスを昇順に並べた列が辞書順で最小になるものを選ぶ）。 i = 1, 2, \ldots, K について、T 上で A_i と B_i を結ぶパスに含まれるすべての辺の色の総 \mathrm{XOR} を P_i とする。 このとき、\{1,2,\dots,K\} のすべての非空部分集合 S に対する「i \in S に対する P_i の総 \mathrm{XOR} 」の最大値を求めよ。
なお、この問題では、クエリで与えられる辺の重み Z_j 、色 D_j の値は暗号化されており、j 番目のクエリの値を正しく復号するには、q=j-1 に対する答えが必要です。 詳しくは、入力の項目を参照してください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \mathbin{\mathrm{XOR}} B は、以下のように定義されます。
- A \mathbin{\mathrm{XOR}} B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \mathbin{\mathrm{XOR}} 5 = 6 となります (二進表記すると: 011 \mathbin{\mathrm{XOR}} 101 = 110)。 一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \mathbin{\mathrm{XOR}} p_2) \mathbin{\mathrm{XOR}} p_3) \mathbin{\mathrm{XOR}} \dots \mathbin{\mathrm{XOR}} p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq U_i < V_i \leq N
- 0 \leq W_i, C_i < 2^{30}
- 1 \leq K \leq 2 \times 10^5
- 1 \leq A_i < B_i \leq N
- 1 \leq Q \leq 10^5
- 1 \leq X_j < Y_j \leq N
- 0 \leq Z_j, D_j < 2^{30}
- 与えられるグラフは連結
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M K U_1 V_1 W_1 C_1 U_2 V_2 W_2 C_2 \vdots U_M V_M W_M C_M A_1 B_1 A_2 B_2 \vdots A_K B_K Q X_1 Y_1 Z'_1 D'_1 X_2 Y_2 Z'_2 D'_2 \vdots X_Q Y_Q Z'_Q D'_Q
ここで、Z'_j, D'_j は Z_j, D_j を暗号化した値であり、0 \leq Z'_j, D'_j < 2^{30} を満たす。 q=j-1 での答えを \mathrm{ans}_{j-1} とすると、Z_j, D_j の値は以下のように復元できる。
- a = (\mathrm{ans}_{j-1} \times 987654321 + 123456789) \bmod 2^{30}
- Z_j = Z'_j \mathbin{\mathrm{XOR}} a
- D_j = D'_j \mathbin{\mathrm{XOR}} a
出力
Q+1 行出力せよ。 j 行目 (1 \leq j \leq Q+1) には q = j-1 に対する答えを出力せよ。
入力例 1
4 3 2 1 2 5 3 2 3 2 6 3 4 3 5 1 2 3 4 2 1 3 680673594 680673596 1 2 766761096 766761102
出力例 1
6 5 5
q = 0 のとき
グラフには以下の 3 本の辺があり、これらがそのまま最小全域木 T を構成します。
- 辺 1 ：頂点 1, 2 を結ぶ、重み 5、 色 3 の辺
- 辺 2 ：頂点 2, 3 を結ぶ、重み 2、 色 6 の辺
- 辺 3 ：頂点 3, 4 を結ぶ、重み 3、 色 5 の辺
このとき、頂点対を結ぶパスの色の \mathrm{XOR} は、
- 頂点 1, 2 を結ぶパス上の辺は辺 1 のみなので P_1 = 3
- 頂点 3, 4 を結ぶパス上の辺は辺 3 のみなので P_2 = 5
となります。 よって、非空部分集合に対する総 \mathrm{XOR} は
- S = \{1\} のとき、P_1 = 3
- S = \{2\} のとき、P_2 = 5
- S = \{1,2\} のとき、P_1 \mathbin{\mathrm{XOR}} P_2 = 6
となり、最大値である 6 が出力されます。
q = 1 のとき
q = 0 の答えを用いて暗号化された値を復元すると、 Z_1 = 1, D_1 = 7 となるため、頂点 1, 3 を結ぶ、重み 1 、色 7 の辺 4 が追加されます。 このとき、最小全域木 T を構成する辺は 2,3,4 になり、頂点対を結ぶパスの色の \mathrm{XOR} は、
- 頂点 1, 2 を結ぶパス上の辺は辺 2, 4 なので P_1 = 6 \mathbin{\mathrm{XOR}} 7 = 1
- 頂点 3, 4 を結ぶパス上の辺は辺 3 のみなので P_2 = 5
となります。 よって、非空部分集合に対する総 \mathrm{XOR} は
- S = \{1\} のとき、P_1 = 1
- S = \{2\} のとき、P_2 = 5
- S = \{1,2\} のとき、P_1 \mathbin{\mathrm{XOR}} P_2 = 4
となり、最大値である 5 が出力されます。
q = 2 のとき
q = 1 の答えを用いて暗号化された値を復元すると、 Z_2 = 2, D_2 = 4 となるため、頂点 1, 2 を結ぶ、重み 2 、色 4 の辺 5 が追加されます。 このとき、最小全域木は、
- 辺 2,3,4 から構成されるもの
- 辺 3,4,5 から構成されるもの
の 2 個ありますが、インデックスが小さい辺を優先して選ぶという条件により、前者が T として選ばれます。 T が q=1 の状態から変化しないため、P_1, P_2 の値もそのまま維持され、引き続き最大値の 5 が出力されます。
入力例 2
7 8 2 3 4 61 32 1 5 27 30 5 6 5 45 3 4 38 18 4 7 62 52 2 3 20 54 3 5 42 8 3 6 50 58 1 2 5 6 5 6 7 544486451 544486435 2 7 544486448 544486444 1 6 326915773 326915738 2 6 326915750 326915753 4 6 326915738 326915732
出力例 2
45 45 60 60 60 60
入力例 3
15 20 7 1 7 1051664880 461254959 4 14 1033711105 325102576 1 5 1018289408 409157878 2 8 970007443 956066717 2 9 966150376 424820668 5 6 937521558 157282293 7 13 932248009 213706061 8 10 910324534 436550654 7 13 877253916 395098507 10 13 872892778 604147733 7 9 854763690 222135021 5 12 809643646 181223530 3 5 770064596 241632507 7 13 713466323 1058069375 9 10 583490032 240127699 7 11 558001197 768909484 1 14 533574948 962910631 5 13 521867120 963200670 11 15 469510353 397063997 7 11 420706245 785977812 5 6 3 9 2 7 4 6 2 9 1 9 3 7 20 9 13 508448241 152928719 12 14 132022057 415748244 4 9 748798040 720294342 8 10 348401067 203725279 5 6 348466136 882723993 5 6 21055102 830461892 8 11 268488046 905480167 1 12 386456687 202378860 4 14 357980987 927331203 8 13 379412682 547581756 11 14 29823388 88947797 1 11 763794847 1029605940 5 6 964866083 272132296 9 14 614749117 1053160459 2 8 976693697 386300653 4 6 982205200 527525952 9 12 910579313 797155817 6 8 809715178 168667179 1 4 838312091 22289074 1 9 1060894323 690587903
出力例 3
1062907980 1070444704 1068416268 1002354669 1002354669 1062271883 1067854932 1067854932 1055899731 1055899731 1049791696 1054870263 1065784672 1065784672 1066022911 1066022911 1066022911 1066022911 1066022911 1059869749 1059869749