Zhang 教授有一个包含 $n$ 个整数的数组。他在纸上写下了一些关于该数组的观察结果。每个观察结果由三个整数 $l_i, r_i$ 和 $s_i$ 描述，这意味着数组在区间 $[l_i, r_i]$ 上所有元素的和模 2 的结果等于 $s_i$。

之后，他尝试仅利用上述观察结果来恢复该数组。显然，存在许多这样的数组。因此，Zhang 教授决定限制数组中每个整数的下界和上界。

给定这些观察结果、下界和上界，求出可能的数组数量以及字典序最小的数组。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 40, 0 \le m \le \frac{n(n+1)}{2}$)，分别表示数组的长度和观察结果的数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i \le y_i \le 10^9$)，表示第 $i$ 个整数的下界和上界。

接下来的 $m$ 行，每行包含三个整数 $l_i, r_i$ 和 $s_i$ ($1 \le l_i \le r_i \le n, 0 \le s_i \le 1$)，表示第 $i$ 个观察结果。

测试数据最多有 110 组，输入总大小不超过 30 KiB。

输出格式

对于每组测试数据，第一行输出可能的数组数量。由于该值可能非常大，请输出其对 $10^9 + 7$ 取模的结果。第二行输出字典序最小的数组。如果可能的数组数量为零，则在第二行仅输出 “-1”（不含引号）。

样例

输入 1

3
3 3
1 10
0 21
3 15
2 2 1
3 3 0
2 3 1
3 0
0 1
1 3
3 4
3 3
1 10
0 21
3 3
2 2 1
3 3 0
2 3 1

输出 1

660
1 1 4
12
0 1 3
0
-1