Join The Future

장 교수는 정수 $n$개로 이루어진 배열을 갖고 있다. 그는 이 배열에 대한 관찰 결과를 종이에 적어 둔다. 각 관찰은 정수 세 개 $l_i$, $r_i$, $s_i$로 주어지며, 배열의 구간 $[l_i, r_i]$에 있는 원소의 합을 2로 나눈 나머지가 $s_i$와 같다는 뜻이다.

장 교수는 이 관찰 결과만으로 배열을 복원하려 한다. 조건을 만족하는 배열은 여러 개일 수 있으므로, 장 교수는 배열의 각 정수가 가질 수 있는 하한과 상한을 정하기로 한다.

관찰 결과와 각 정수의 하한, 상한이 주어졌을 때, 가능한 배열의 개수와 사전순으로 가장 앞서는 배열을 구하라.

입력에는 여러 개의 테스트 케이스가 들어 있다. 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 정수 $n$과 $m$이 주어진다 ($1 \le n \le 40$, $0 \le m \le \frac{n(n+1)}{2}$). $n$은 배열의 길이이고, $m$은 관찰 결과의 개수이다.

이어서 $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개이며, 전체 입력 크기는 30KiB 이하이다.

각 테스트 케이스마다 첫 줄에는 가능한 배열의 개수를 $10^9 + 7$로 나눈 나머지로 출력한다. 둘째 줄에는 사전순으로 가장 앞서는 배열을 출력한다. 조건을 만족하는 배열이 없으면 둘째 줄에 "-1"을 출력한다.