AT_bogosortcontest_div1_f Path XOR on MST

$ 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 $ の順番によらないことが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ に対する答えを出力せよ。

### Sample Explanation 1 #### $ 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 $ が出力されます。 ### Constraints - $ 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} $ - 与えられるグラフは連結 - 入力される数値はすべて整数