该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

星港的维护系统正在为 $n$ 台机器人写入校验码，第 $i$ 台机器人的校验码为非负整数 $a_i$，且不超过 $k$ 位二进制数。

系统记录了 $m$ 条联动日志。第 $i$ 条日志包含三个整数 $x_i,y_i,z_i$，表示第 $x_i$ 与第 $y_i$ 台机器人的校验码按位与结果应当恰好为 $z_i$，即：

其中 $x\mathbin{\&}y$ 表示整数 $x,y$ 的按位与。日志可能互相矛盾，因此满足全部日志的校验码方案不一定存在。

请你判断是否存在一组合法的校验码。若存在，输出 $a_1+a_2+\cdots+a_n$ 的最小可能值。

输入格式

本题有多组数据。第一行一个正整数 $T\ (1\le T\le 5\times10^5)$，表示数据组数。

对于每组数据：

第一行三个整数 $n,m,k\ (1\le n,m\le2\times10^5,\ 1\le k<30)$，分别表示机器人数量、联动日志数量与校验码的二进制长度上限。

接下来 $m$ 行，每行三个整数 $x_i,y_i,z_i\ (1\le x_i,y_i\le n,\ 0\le z_i<2^k)$，表示一条联动日志。

保证所有数据中 $n$ 的和与 $m$ 的和分别不超过 $5\times10^5$。

注意：$x_i$ 与 $y_i$ 可以相等；多条日志也可能询问同一对机器人。

输出格式

对于每组数据：

输出一行一个整数。若不存在满足全部日志的校验码方案，输出 -1；否则输出所有校验码之和的最小可能值。

输入输出样例 #1

输入 #1

5
3 3 1
1 2 0
1 3 0
2 3 1
3 2 30
1 2 1073741823
2 3 1073741823
3 3 1
1 2 1
1 3 1
2 3 0
100 1 16
1 1 4514
3 4 3
1 1 5
2 2 6
1 2 4
1 3 5

输出 #1

2
3221225469
-1
4514
16

说明

第一组数据中，取 $(a_1,a_2,a_3)=(0,1,1)$ 即可满足全部日志，且和为 $2$。

第三组数据中，前两条日志均要求对应两个校验码的最低位为 $1$，从而 $a_1,a_2,a_3$ 的最低位都必须为 $1$；但第三条日志要求 $a_2\mathbin{\&}a_3=0$，产生矛盾。