题目描述

提示：题目描述中的“向量“可以理解为一个数组。

小圈是一名运筹学大师。她正在研究如下问题：

给定 $m$ 维 01 空间内 $n$ 个约束，满足 $AX = b$，和一个 $m$ 维系数向量 $C \in R^{m}$。你要找到一个满足约束的 $m$ 维列向量 $X$，最大化 $C \cdot X$。

这个问题是一个过于普通的 01 整数规划问题，小圈同学已经提出了一个关于 $n$ 和 $m$ 的多项式算法来解决它。在论文写作过程中，小圈同学尝试展望一个更新的问题，即把限制组成的非齐次线性方程组改为模 $2$ 意义下的方程组。这下小圈不会了，所以请你来解决这个问题。

给定一个 $n$ 行 $m$ 列的矩阵 $a_{n \times m}$，一个 $n$ 维列向量 $b=[b_1, b_2, \dots b_n]^T$，和一个 $m$ 维系数向量 $C=[c_1,c_2,\dots c_m]^T$，其中 $a_{i,j} \in \{0,1\}$，$b_i \in \{0,1\}$，$c_i \in [1, 10^9] \cap \Z$。你要找到一个 $m$ 维列向量 $X = [x_1, x_2, \dots x_m]^T$，其中 $x _ i \in \{0, 1\}$，并且满足：

• $b_i \equiv \sum_{j = 1}^m a_{i,j}\times x_j \pmod 2$，$i = 1,2,3,\dots , n$。

最大化 $\sum_{j = 1}^m c_j x_j$，输出方案。

输入格式

本题单个测试点内有多组测试数据。第一行是一个整数 $T$，表示数据组数。对每组数据，按如下格式输入：

第一行是两个整数，表示 $n,m$。
接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $a_{n\times m}$。
接下来一行 $n$ 个整数，表示 $b_1, b_2, \dots b_n$。
接下来一行 $m$ 个整数，表示 $c_1, c_2, \dots c_m$。

输出格式

对每组数据，按如下格式输出：

• 如果不存在符合要求的 $X$，输出一行一个字符串 $-1$。
• 否则在第一行输出最大的 $\sum_{j = 1}^m c_j x_j$，第二行输出 $m$ 个整数，第 $i$ 个整数表示最大化方案里 $x_i$ 的值。

样例

样例 1 输入

3
2 2
0 1
1 0
1 1
1 1
2 2
0 0
1 1
1 1
1 1
2 2
0 0
1 1
0 1
1 10

样例 1 输出

2
1 1
-1
10
0 1

样例 2

见下发文件 matrix2.in 和 matrix2.ans，该样例满足测试点 $1 \sim 2$ 的限制。

数据范围和约定

本题共包含 $10$ 个测试点，每个测试点 $10$ 分。

对 $100\%$ 的数据，$1 \leq n, m \leq 60$，$1 \leq n + m \leq 60$，$1 \leq T \leq 5$，$0 \leq a_{i,j}, b_i \leq 1$，$1 \leq c_i \leq 10^9$。