序列奇偶

有�个整数，其中第�个整数在[��, �� ]之间。

还有�个限制，每个限制给你�� , �� , �� ，要求第�� 到第�� 个数字加起来对 2 取模余数 为�� 。

你想知道有多少种整数序列满足上面的限制，输出答案对109 + 7 取模的结果。

然后输出字典序最小的整数序列，也就是首先要求第一个整数最小，在第一个整最 小的基础上要求第二个最小，依次类推。

输入格式 第一行，两个整数�, �。

接下来�行，每行两个整数�� , �� 。

接下来�行，每行三个整数�� , �� , �� ，表示一个限制。

输出格式 第一行，一个整数，表示方案数，对109 + 7 取模的结果。

接下来一行，输出�个数字，表示字典序最小的序列。如果不存在，输出一个−1。

样例输入 1 3 3 1 10 0 21 3 15 2 2 1 3 3 0 2 3 1

样例输出 1 660 1 1 4

样例输入 2 3 3 1 10 0 21 3 3 2 2 1 3 3 0 2 3 1

样例输出 2 0 -1

样例输入输出 3 见下发文件。

数据规模 共 10 组数据。

测试点 1 满足 1 ≤ � ≤ 5, �� ≤ 10。

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

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

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

对于 100% 的数据，满足 1 ≤ � ≤ 40,0 ≤ � ≤ 100,0 ≤ �� ≤ �� ≤ 109 , 1 ≤ �� ≤ �� ≤ �。