Join The Future

Professor Zhang has an array of $n$ integers. He writes down some observations about the array on paper. Each observation is described by three integers $l_i$, $r_i$, and $s_i$, which means that the sum of elements modulo 2 on the interval $[l_i, r_i]$ of the array is equal to $s_i$.

After that, he tries to recover the array using only these observations. Many arrays may satisfy them, so Professor Zhang limits the lower and upper bound of each integer in the array.

Given the observations, the lower bounds, and the upper bounds, find the number of possible arrays and the lexicographically smallest array.

There are multiple test cases. The first line of input contains an integer $T$, the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n \le 40$, $0 \le m \le \frac{n(n+1)}{2}$): the length of the array and the number of observations.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i \le y_i \le 10^9$): the lower and upper bound of the $i$-th integer.

Each of the next $m$ lines contains three integers $l_i$, $r_i$, and $s_i$ ($1 \le l_i \le r_i \le n$, $0 \le s_i \le 1$), denoting the $i$-th observation.

There are at most $110$ test cases, and the total input size is at most 30 kibibytes.

For each test case, output the number of possible arrays on the first line, modulo $10^9 + 7$. On the second line, output the lexicographically smallest array. If no array is possible, output "-1" on the second line.