Description

你对自己秘密基地设计中的陷阱感到厌倦，决定采用一种经典但总是令人愉快的装置——“旋转刀片”。你订购了一块非常重的金属板，准备从中切割出刀片；在金属板上会绘制一个均匀的 $C$ 行 $R$ 列的方格。你已经确定了刀片的最佳形状——你将首先切割出一个 $K \times K$ 的大正方形方格，其中 $K \geq 3$。然后，你会将该正方形的四个 $1 \times 1$ 的角格切掉，最终得到一个“刀片”。确定好这些后，你就开始等待金属板的到来。

当金属板到达时，你震惊地发现板材有瑕疵！你原本期望每个格子的质量都是 $D$，但实际上由于厚度的差异，每个格子的质量会有些许变化。这很糟糕，因为你想要在刀片的正中心插入一个轴并让其高速旋转，因此刀片的质心必须恰好位于其中心。二维物体的质心定义见下文。

给定方格和每个格子的质量，求你能切割出的最大尺寸的刀片，使得其质心恰好位于中心。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据第一行为三个整数：$R$、$C$ 和 $D$——方格的行数、列数以及你期望每个格子的质量。接下来的 $R$ 行每行包含 $C$ 个数字 $w_{ij}$，表示实际质量与期望质量的差值。每个格子的实际质量为 $D + w_{ij}$，其中 $0 \leq w_{ij} \leq 9$。

Output Format

对于每个测试用例，输出一行，格式为 “Case #$x$: $K$”，其中 $x$ 是测试用例编号（从 $1$ 开始），$K$ 是你能切割出的最大刀片尺寸。如果不存在尺寸至少为 $3$ 且满足条件的刀片，输出 “IMPOSSIBLE”。

2
6 7 2
1111111
1122271
1211521
1329131
1242121
1122211
3 3 7
123
234
345

Case #1: 5
Case #2: IMPOSSIBLE

Hint

样例说明

二维物体的质心正式定义为一个点 $c$。如果你对物体中的所有点 $p$ 计算 $(p - c) \times \text{mass}(p)$ 的和，结果必须为 $0$。其中 $p$、$c$ 和 $0$ 都是二维向量。这个定义同样适用于将每个格子视为一个“点”，其全部质量集中在中心。

在现实生活中，你可以把手指放在一个平面物体的质心下方，并让物体平衡在手指上，它不会倾倒。

举例来说，在第二个样例测试中，唯一可行的刀片是 $3 \times 3$ 的刀片（去掉四个角），其质心位于点 $(1.54, 1.46)$，假设金属板左下角坐标为 $(0, 0)$，坐标分别向右和向上递增。可以通过以下等式验证：$(-1.04, 0.04) \times 9 + (-0.04, 1.04) \times 9 + (-0.04, 0.04) \times 10 + (-0.04, -0.96) \times 11 + (0.96, 0.04) \times 11 = (0, 0)$。

数据范围

• $1 \leq T \leq 20$。
• $0 \leq w_{ij} \leq 9$。
• 输入文件大小不超过 625KB。

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

• $3 \leq R \leq 10$。
• $3 \leq C \leq 10$。
• $1 \leq D \leq 100$。
• 时间限制：3 秒。

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

• $3 \leq R \leq 500$。
• $3 \leq C \leq 500$。
• $1 \leq D \leq 10^6$。
• 时间限制：6 秒。

由 ChatGPT 4.1 翻译