6252：Subway Chasing

Mr. Panda and God Sheep are roommates and working in the same company. They always take subway to work together. There are $N$ subway stations on their route, numbered from 1 to $N$. Station 1 is their home and station $N$ is the company.
One day, Mr. Panda was getting up later. When he came to the station, God Sheep has departed $X$ minutes ago. Mr. Panda was very hurried, so he started to chat with God Sheep to communicate their positions. The content is when Mr. Panda is between station $A$ and $B$, God Sheep is just between station $C$ and $D$.
$B$ is equal to $A + 1$ which means Mr. Panda is between station $A$ and $A + 1$ exclusive, or $B$ is equal to $A$ which means Mr. Panda is exactly on station $A$. Vice versa for $C$ and $D$. What’s more, the communication can only be made no earlier than Mr. Panda departed and no later than God Sheep arrived.
After arriving at the company, Mr. Panda want to know how many minutes between each adjacent subway stations. Please note that the stop time at each station was ignored.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
Each test case starts with a line consists of 3 integers $N$, $M$ and $X$, indicating the number of stations, the number of chat contents and the minute interval between Mr. Panda and God Sheep. Then $M$ lines follow, each consists of 4 integers $A$, $B$, $C$, $D$, indicating each chat content.
$1 \leq T \leq 30$
$1 \leq N, M \leq 2000$
$1 \leq X \leq 10^9$
$1 \leq A, B, C, D \leq N$
$A \leq B \leq A + 1$
$C \leq D \leq C + 1$

For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting from 1) and $y$ is the minutes between stations in format $t_1, t_2, . . . , t_{N-1}$. $t_i$ represents the minutes between station $i$ and $i + 1$. If there are multiple solutions, output a solution that meets $0 < t_i \leq 2 \times 10^9$. If there is no solution, output “IMPOSSIBLE” instead.