[Ctsc2005]玩具的重量weight

冰冰有三个玩具：皮卡秋、维妮孙悟空和芭比娃娃。她不知道这些玩具的具体重量，重量采用 NOI 单位，但知道每个玩具重量的初始范围：

冰冰希望进一步缩小这些范围。佳佳有一个电子天平，它不仅能判断天平两边是否一样重，还能给出左边比右边重多少。天平的左右两边均可放置任意多件玩具。

佳佳为了考验冰冰，规定在所有称量中，每个玩具最多只能在天平左侧出现一次、在右侧出现一次。例如，如果皮卡秋已经被放在天平左侧称量过，就不能再次放在左侧，但仍可放在右侧。

对于上面的三个玩具，冰冰进行了两次称量：

• 第一次将皮卡秋放在左侧、维妮孙悟空放在右侧，测得左侧比右侧重 $-1$ 个单位；
• 第二次将维妮孙悟空放在左侧、芭比娃娃放在右侧，测得左侧比右侧重 $1$ 个单位。

结合初始重量范围，可以确定皮卡秋、维妮孙悟空和芭比娃娃的重量分别为 $3$、$4$、$3$。

冰冰以后还会买很多玩具。请编写程序，根据所有玩具的初始重量范围和称量结果，计算每个玩具最精确的整数重量下限和上限。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示玩具数量和称量次数。

第二行包含 $2n$ 个整数。第 $2i-1$ 个数和第 $2i$ 个数分别表示第 $i$ 个玩具的初始重量下限和初始重量上限。

接下来 $m$ 行，每行描述一次称量。每行前三个整数 $L$、$R$、$D$ 分别表示天平左侧的玩具数量、右侧的玩具数量，以及左侧总重量减去右侧总重量所得的差，其中 $L,R\ge 0$。

随后给出 $L$ 个整数，表示天平左侧的玩具编号；再给出 $R$ 个整数，表示天平右侧的玩具编号。

输入保证每个玩具在天平的每一侧最多出现一次。

输出格式

如果不存在满足所有初始范围和称量结果的重量方案，仅输出一个整数 $-1$。

否则，输出 $2n$ 个整数。第 $2i-1$ 个数和第 $2i$ 个数分别表示第 $i$ 个玩具所有可能整数重量中的最小值和最大值。

样例输入

样例 $1$：

3 2
1 3 2 4 3 5
1 1 -1 1 2
1 1 1 2 3

样例 $2$：

3 1
1 5 2 5 1 3
2 1 1 1 2 3

样例输出

样例 $1$：

3 3 4 4 3 3

样例 $2$：

1 2 2 3 2 3

样例解释

在样例 $2$ 中，天平左侧放置了玩具 $1$ 和玩具 $2$，右侧放置了玩具 $3$，左侧比右侧重 $1$ 个单位。

结合各玩具的初始重量范围，可以确定三个玩具最精确的重量范围依次为 $[1,2]$、$[2,3]$ 和 $[2,3]$。

数据范围

• $3\le n\le 200$；
• $1\le m\le 100$；
• 玩具的重量上限不超过 $2\times 10^4$；
• $L,R\ge 0$；
• 每个玩具在天平的每一侧最多出现一次。

来源与许可

本题为 CTSC 2005 试题「玩具的重量」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 2
1 3 2 4 3 5
1 1 -1 1 2
1 1 1 2 3

输出

3 3 4 4 3 3

样例 2

输入

3 1
1 5 2 5 1 3
2 1 1 1 2 3

输出

1 2 2 3 2 3