Description

著名的 Slate Modern 画廊专注于最新的艺术潮流：遵循严格规则的灰度画作。画廊中的每一幅画都必须是一个有 $R$ 行 $C$ 列的网格。网格中的每个格子都被涂上一个正整数的亮度值；为了避免画面过于刺眼，任何两个有公共边（不仅仅是角）的格子的亮度值之差不能超过 $D$。

你的艺术家朋友 Cody-Jamal 正在为画廊创作一幅画。昨晚，他灵感迸发，已经在 $N$ 个不同的特定格子里填入了某些正整数亮度值。你今天才告诉他画廊的规则，现在他想知道，是否有可能为剩下的所有格子填入正整数亮度值，并完成这幅画，同时不违反画廊的规则。如果可以，他希望所有亮度值的总和尽可能大，以节省黑色颜料。你能帮他求出这个最大可能的亮度总和，或者判断任务是否不可能完成吗？由于结果可能非常大，你只需要输出结果对质数 $10^9 + 7$（$1000000007$）取余后的值。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为四个整数：$R$、$C$、$N$ 和 $D$，含义如上所述。接下来的 $N$ 行，每行有三个整数 $R_i$、$C_i$ 和 $B_i$，表示第 $R_i$ 行第 $C_i$ 列的格子的亮度值为 $B_i$。网格的行和列编号均从 1 开始。

Output Format

对于每组测试数据，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最大可能的亮度总和对 $10^9 + 7$ 取余的结果；如果无法完成画作，则输出 IMPOSSIBLE。

4
2 3 2 2
2 1 4
1 2 7
1 2 1 1000000000
1 2 1000000000
3 1 2 100
1 1 1
3 1 202
2 2 2 2
2 1 1
2 2 4

Case #1: 40
Case #2: 999999986
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE

Hint

样例解释

样例 1 中，最优的填法如下：

6 7 9
4 6 8

总和为 $40$。

样例 2 中，最优的填法如下：

2000000000 1000000000

总和为 $3000000000$；对 $10^9 + 7$ 取余后为 $999999986$。

样例 3 中，任务无法完成。无论你为第 2 行的格子选择什么值，它与已填的相邻格子的亮度差都会超出允许范围。

样例 4 中，Cody-Jamal 已经填入的两个格子的亮度值差距过大，因此无法继续完成画作。

数据范围

• $1 \leq T \leq 100$。
• $1 \leq N \leq 200$。
• $1 \leq D \leq 10^9$。
• $1 \leq R_i \leq R$，对于所有 $i$。$1 \leq C_i \leq C$，对于所有 $i$。$1 \leq B_i \leq 10^9$，对于所有 $i$。（注意，上界仅适用于 Cody-Jamal 已经填入的格子。你可以为其他格子分配大于 $10^9$ 的亮度值。）
• $N < R \times C$。（至少有一个空格子。）
• 对于所有 $i \neq j$，有 $R_i \neq R_j$ 或 $C_i \neq C_j$。（所有已知格子均不相同。）

小数据范围（5 分，测试点 1 - 可见）

• 时间限制：10 秒。
• $1 \leq R \leq 200$。
• $1 \leq C \leq 200$。

大数据范围（26 分，测试点 2 - 隐藏）

• 时间限制：20 秒。
• $1 \leq R \leq 10^9$。
• $1 \leq C \leq 10^9$。

由 ChatGPT 4.1 翻译