熊猫先生和羊神是室友，在同一家公司工作。他们总是乘地铁一起去上班。他们的路线上有 $N$ 个地铁站，编号从 $1$ 到 $N$。$1$ 号站是他们的家，$N$ 号站是公司。

有一天，熊猫先生起晚了。当他到达车站时，羊神已经在 $X$ 分钟前出发了。熊猫先生非常着急，于是他开始与羊神聊天以交流各自的位置。聊天内容是：当熊猫先生在车站 $A$ 和 $B$ 之间时，羊神正好在车站 $C$ 和 $D$ 之间。

$B = A + 1$ 表示熊猫先生在车站 $A$ 和 $A + 1$ 之间（不含端点），或者 $B = A$ 表示熊猫先生正好在车站 $A$。$C$ 和 $D$ 的情况同理。此外，交流只能在熊猫先生出发后且在羊神到达公司前进行。

到达公司后，熊猫先生想知道每两个相邻地铁站之间需要多少分钟。请注意，每个车站的停留时间被忽略了。

输入格式

第一行输入包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含 $3$ 个整数 $N, M$ 和 $X$，分别表示车站数量、聊天内容数量以及熊猫先生和羊神出发的时间间隔。 接下来 $M$ 行，每行包含 $4$ 个整数 $A, B, C, D$，表示每一次聊天内容。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是相邻车站之间的分钟数，格式为 $t_1, t_2, \dots, t_{N-1}$。$t_i$ 表示车站 $i$ 和 $i + 1$ 之间的分钟数。如果存在多个解，输出一个满足 $0 < t_i \le 2 \times 10^9$ 的解。如果无解，则输出 "IMPOSSIBLE"。

数据范围

• $1 \le T \le 30$
• $1 \le N, M \le 2000$
• $1 \le X \le 10^9$
• $1 \le A, B, C, D \le N$
• $A \le B \le A + 1$
• $C \le D \le C + 1$

样例

输入 1

2
4 3 2
1 1 2 3
2 3 2 3
2 3 3 4
4 2 2
1 2 3 4
2 3 2 3

输出 1

Case #1: 1 3 1
Case #2: IMPOSSIBLE

说明

在第二个测试用例中，当羊神经过第三个车站时，熊猫先生还没有到达第二个车站。他们不可能同时在第二个车站和第三个车站之间。