题目描述

有$n$个整数，其中第$i$个整数在$[x_i,y_i]$之间。 还有$m$个限制，每个限制给你$l_i,r_i,s_i$，要求第$l_i$到第$r_i$个数字加起来对$2$取模余数为$s_i$。 你想知道有多少种整数序列满足上面的限制，输出答案对$10^9 + 7$ 取模的结果。 然后输出字典序最小的整数序列，也就是首先要求第一个整数最小，在第一个整最小的基础上要求第二个最小，依次类推。

输入格式

第一行，两个整数$n, m$。 接下来$n$行，每行两个整数$x_i,y_i$。 接下来$m$行，每行三个整数$l_i,r_i,s_i$，表示一个限制。

输出格式

第一行，一个整数，表示方案数，对$10^9 + 7$取模的结果。 接下来一行，输出$n$个数字，表示字典序最小的序列。如果不存在，输出一个$−1$。

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

660
1 1 4

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

0
-1

样例输入输出 3

见下发文件。

数据规模

共 10 组数据。 测试点 1 满足 $1 ≤ n ≤ 5, y_i ≤ 10$。

测试点 2,3 满足 $1 ≤ n ≤ 5$。

测试点 4,5 满足 $1 ≤ n ≤ 20$。

测试点 6,7 满足 $1 ≤ n ≤ 30$。

对于 100% 的数据，满足 $1 ≤ n ≤ 40$,$0 ≤ m ≤ 100,$$0 ≤ x_i ≤ y_i ≤ 10^9, 1 ≤ l_i ≤ r_i ≤ n$。

附件

附件下载