CF1633E.Spanning Tree Queries

You are given a connected weighted undirected graph, consisting of $n$ vertices and $m$ edges.

You are asked $k$ queries about it. Each query consists of a single integer $x$. For each query, you select a spanning tree in the graph. Let the weights of its edges be $w_1, w_2, \dots, w_{n-1}$. The cost of a spanning tree is $\sum \limits_{i=1}^{n-1} |w_i - x|$ (the sum of absolute differences between the weights and $x$). The answer to a query is the lowest cost of a spanning tree.

The queries are given in a compressed format. The first $p$ $(1 \le p \le k)$ queries $q_1, q_2, \dots, q_p$ are provided explicitly. For queries from $p+1$ to $k$, $q_j = (q_{j-1} \cdot a + b) \mod c$.

Print the xor of answers to all queries.

给你一个包含 $n$ 个顶点和 $m$ 条边的连通带权无向图。

你需要回答 $k$ 个查询。每个查询给出一个整数 $x$。对于每个查询，你需要在图中选择一棵生成树。设该生成树各边的权重为 $w_1, w_2, \dots, w_{n-1}$。该生成树的代价定义为 $\sum \limits_{i=1}^{n-1} |w_i - x|$（即所有边权与 $x$ 的绝对差之和）。查询的答案即为所有可能生成树中的最小代价。

这些查询以压缩形式给出：前 $p$ 个查询（$1 \le p \le k$）$q_1, q_2, \dots, q_p$ 被显式给出；而从第 $p+1$ 个到第 $k$ 个查询，按如下方式递推生成：$q_j = (q_{j-1} \cdot a + b) \mod c$。

请输出所有查询答案的异或（xor）值。

The first line contains two integers $n$ and $m$ ($2 \le n \le 50$; $n - 1 \le m \le 300$) — the number of vertices and the number of edges in the graph.

Each of the next $m$ lines contains a description of an undirected edge: three integers $v$, $u$ and $w$ ($1 \le v, u \le n$; $v \neq u$; $0 \le w \le 10^8$) — the vertices the edge connects and its weight. Note that there might be multiple edges between a pair of vertices. The edges form a connected graph.

The next line contains five integers $p, k, a, b$ and $c$ ($1 \le p \le 10^5$; $p \le k \le 10^7$; $0 \le a, b \le 10^8$; $1 \le c \le 10^8$) — the number of queries provided explicitly, the total number of queries and parameters to generate the queries.

The next line contains $p$ integers $q_1, q_2, \dots, q_p$ ($0 \le q_j \lt c$) — the first $p$ queries.

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 50$；$n - 1 \le m \le 300$）—— 分别表示图中顶点的数量和边的数量。

接下来的 $m$ 行，每行描述一条无向边：三个整数 $v$、$u$ 和 $w$（$1 \le v, u \le n$；$v \neq u$；$0 \le w \le 10^8$）—— 表示该边所连接的两个顶点及其权重。注意：一对顶点之间可能存在多条边。所有边构成一个连通图。

接下来的一行包含五个整数 $p$、$k$、$a$、$b$ 和 $c$（$1 \le p \le 10^5$；$p \le k \le 10^7$；$0 \le a, b \le 10^8$；$1 \le c \le 10^8$）—— 分别表示显式给出的查询数量、查询总数以及用于生成查询的参数。

下一行包含 $p$ 个整数 $q_1, q_2, \dots, q_p$（$0 \le q_j \lt c$）—— 表示前 $p$ 个查询。

Print a single integer — the xor of answers to all queries.

输出一个整数——所有查询答案的异或值。

The queries in the first example are $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0$. The answers are $11, 9, 7, 3, 1, 5, 8, 7, 5, 7, 11$.

The queries in the second example are $3, 0, 2, 1, 6, 0, 3, 5, 4, 1$. The answers are $14, 19, 15, 16, 11, 19, 14, 12, 13, 16$.

The queries in the third example are $75, 0, 0, \dots$. The answers are $50, 150, 150, \dots$.

第一个示例中的查询序列为 $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0$，对应答案为 $11, 9, 7, 3, 1, 5, 8, 7, 5, 7, 11$。

第二个示例中的查询序列为 $3, 0, 2, 1, 6, 0, 3, 5, 4, 1$，对应答案为 $14, 19, 15, 16, 11, 19, 14, 12, 13, 16$。

第三个示例中的查询序列为 $75, 0, 0, \dots$，对应答案为 $50, 150, 150, \dots$。