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

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

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

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

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

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

输入格式

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

对于每组数据：

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

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

接下来 $m$ 行，每行开头三个整数 $L,R,D$ 分别表示左侧玩具个数，右侧玩具个数，两侧玩具重量差（$D<0$ 表示左侧轻，$D>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\le T\le 20,2\le n\le 200,1\le m\le 100,1\le b_i\le c_i\le 30000,L,R\ge 0,|D|\le {10}^9$。

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

时间限制：$5\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

来源

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

特别鸣谢：楼天成