冰冰有三种玩具：皮卡丘，孙悟空和芭比娃娃。他不知道玩具的确切重量，但是他知道每个玩具的重量在某个区间内，如下表：

嘉嘉有一个电子天平，可以称量左右两侧的重量差异。由于秤盘很大，两侧可以放任意多的玩具。

冰冰向嘉嘉借天平以确定玩具的重量，嘉嘉给了冰冰一个挑战：每个玩具放在两侧分别至多一次。

冰冰接受了这个挑战，用了两次天平，如下所示：

于是冰冰得到了玩具的确切重量：

一个月后，冰冰有了 $n$ 个玩具，使用了 $m$ 次天平（同样满足上述条件），你需要告诉她每个玩具的可能重量区间。

输入格式

本题多测，最后输入一行 0 0 表示评测结束。

对于每组数据：

第一行两个整数 $n,m$ 分别表示玩具个数和天平使用次数。

第二行 $2n$ 个整数，第 $2i-1$ 个整数 $b_i$ 表示第 $i$ 个玩具的最小可能重量，$2i$ 个整数 $c_i$ 表示第 $i$ 个玩具的最大可能重量。

接下来 $m$ 行，每行开头三个整数 $L,R,D$ 分别表示左侧玩具个数，右侧玩具个数，两侧玩具重量差（$D\lt 0$ 表示左侧轻，$D\gt 0$ 表示右侧轻）。

• 接下来 $L$ 个整数表示左侧玩具的编号。
• 接下来 $R$ 个整数表示右侧玩具的编号。

输出格式

对于第 $i$ 组数据，首先输出 Case i:，若有解，输出 $2n$ 个整数表示每个玩具的重量区间，否则输出 -1。

样例

input

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

output

Case 1: 3 3 4 4 3 3
Case 2: -1
Case 3: 1 2 2 3 2 3

数据范围与提示

令 $T$ 为数据组数。

保证 $1\leq T\leq 20, 2\leq n\leq 200, 1\leq m\leq 100, 1\leq b_i\leq c_i\leq 30000, L,R\geq 0, |D|\leq 10^9$。

保证每个玩具至多在左右秤盘各出现一次，一个玩具可能在一次称量中出现两次。

时间限制：$5\texttt{s}$

空间限制：$256\texttt{MB}$

来源

Uva Online Judge，CTSC 2005，题目作者刘汝佳。

特别鸣谢：楼天成