题目背景

在茫茫宇宙中……

题目描述

有一群生物 ccj，他们发现了一个超星系群。其中有 $n$ 个恒星，$m$ 条双向星际航线，每条星际航线都需要消耗 $val_i$ 的燃料值。两个恒星不属于同一个星系当且仅当他们之间没有任何航线，且没有任何路径可以到达。只有每个恒星才可以为飞船补充燃料。每次航行的路线都是一条简单路径。由于燃料系统过于简陋，每个燃料罐只能用于一次航行。他们的首长 ccj 想在其中一个恒星上建立基地。但是 ccj 花了太多钱购买高速飞船，没有太多钱购买燃料罐，所以他对于两个恒星之间的航行一定选择最经济的航行方式，购买最小的燃料罐。他想问你，在基地要备多少的燃料总量，使得在任意一个恒星上建立基地都能从那个基地分别到达那个星系的其他所有恒星。

但是，这个超星系群发生了战争，一些黑洞改变了这里的空间结构。这群生物只知道每条航线花费的燃料值，找不到连接的两个恒星。但是他们的科学家发现了一个性质：每个战争有一个标志值 $q$，航线有不同的排列方式，对于其中一种排列，第 $i$ 条航线连接着 $((q^{i} \bmod 2^{32}+i \times val_i) \bmod n+n) \bmod n+1$ 和 $((q^{i} \bmod 2^{32}-i \times val_i) \bmod n+n) \bmod n+1$ 两个恒星。运算方式为无符号整型运算。如果连接的两个恒星一样，说明科学家计算有误，忽略这条航线。ccj 的目标改变了。他想知道对于所有星系的构成情况，最少需要准备多少的燃料总量，使得在这种结构中，在任意一个恒星上建立基地都能分别到达该结构下那个恒星所处星系的其他所有恒星。

你需要输出航线排列顺序。

输入格式

第一行三个正整数 $n$，$m$ 和 $q$，表示有 $n$ 个恒星，$m$ 条航线，战争标志值 $q$。

第二行 $m$ 个正整数 $val_i$，表示第 $i$ 条航线消耗 $val_i$ 的燃料值。

输出格式

第一行一个正整数 $ans$，表示 ccj 需要你求的数值。

从第二行到第 $m+1$ 行，每行输出一个整数，第 $i$ 行输出这个排列下的 $val_{i-1}$。

3 5 2
1 2 3 4 5

1
5
4
2
3
1

提示

样例解释：

这 $5$ 条航线分别是：

$2$ 与 $2$ 往返，花费燃料 $5$

$1$ 与 $1$ 往返，花费燃料 $4$

$3$ 与 $3$ 往返，花费燃料 $2$

$2$ 与 $2$ 往返，花费燃料 $3$

$1$ 与 $2$ 往返，花费燃料 $1$

前四条航线被忽略，故有四个恒星系，$\{1,2\},\{3\},\{4\},\{5\}$

基地建在 $1$ 时，从 $1$ 到 $2$ 需要购买燃料量为 $1$ 的燃料罐，可以发现，没有其他比这个更优的答案。

$2 \le n \le 100\quad 1 \le m \le 40\quad 0 \le q \le 10^9\quad 0 \le val_i \le 1000$

你的答案只需要比std优秀或者和std一样且方案正确即可

1~4数据都为最优答案，5~10数据都为次优答案

此题会给出第10个数据的输入 输入数据

详细范围参见”标程“

数据均为随机构造，请注意常数！