P16119 [USTCPC 2026] Gradient Descent

“呼～终于把离散梯度的公式搞懂了！”克露丝卡尔酱伸了个懒腰，面前的笔记本上画满了网格。 坐在旁边的同学探过头来：“克露丝卡尔酱还在研究那个梯度下降问题吗？” “嗯嗯！我在想，怎么在保证找到最小值的前提下让算法跑得快一点呢？”克露丝卡尔酱歪着头，露出困惑的表情。 “啊，那不就是要求最大学习率吗？不过还要考虑边界情况呢。”同学随口说道。 克露丝卡尔酱眼睛一亮：“对呀！让我们来算算吧～”

对于网格标量场 $f$，按以下方式定义 $(i,j)$ 处的离散梯度： $$\begin{cases} \frac{\Delta f}{\Delta x}=\frac{f_{i+1,j}-f_{i-1,j}}{2}\\ \frac{\Delta f}{\Delta y}=\frac{f_{i,j+1}-f_{i,j-1}}{2} \end{cases}$$ 若 $(i,j)$ 位于网格边界，则相应地只计算单侧差分，并且不需要除以 $2$，例如对于 $i=1$ 的点：$\frac{\Delta f}{\Delta x}=f_{i+1,j}-f_{i,j}$。 使用如下的梯度下降算法寻找网格中的最小值： $$ \begin{cases} i\leftarrow i-\eta\cdot\frac{\Delta f}{\Delta x}\\ j\leftarrow j-\eta\cdot\frac{\Delta f}{\Delta y} \end{cases} $$ 其中 $\eta$ 称为学习率，为了保证步长总为整数，需要保证 $\eta$ 为偶数。若梯度下降过程中坐标超出了网格范围，则直接结束。 给定 $n\times m$ 尺寸的网格标量场以及初始坐标（保证初始坐标不是全局最小值），在能够找到全局最小值的前提下，学习率最大可以设置为多少？ 只要在梯度下降过程中经过了取到全局最小值的位置，即视为找到了全局最小值。

首先输入一行，包含一个整数 $T$ ($1\le T\le 25000$)，表示测试数据组数。 每组数据首先输入一行，包含四个整数，分别表示网格的行数 $n$ ($n\ge 2$)、列数 $m$ ($m\ge 2$)，初始位置所在行 $r$ ($1\le r\le n$)、所在列 $c$ ($1\le c\le m$)。保证 $nm\le 10^5$。 接下来输入 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数表示 $f_{i,j}$ ($\lvert f_{i,j}\rvert\le 100$)。保证 $f_{r,c}\neq\min{f}$。 保证 $\sum nm\le 10^5$。

输出 $T$ 行，表示每组数据的答案。若无论学习率是多少，都无法找到全局最小值，输出 `Impossible`，否则输出能够找到全局最小值的最大的学习率。 注意：本题中的学习率必须为大于零的偶数。

对于第一组样例，由于初始位置的梯度为 $0$，因此坐标将永远不变，无法到达取到全局最小值的位置。 对于第二组样例，当 $\eta=4$ 时，坐标变化的过程为： $(1,3)\to(5,1)\to(5,5)$，此时取到全局最小值 $1$，因此 $\eta=4$ 满足条件。而任何大于 $4$ 的学习率均会导致第一次梯度下降就超出网格范围，因此答案为 $4$。