You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

“呼～终于把离散梯度的公式搞懂了！”克露丝卡尔酱伸了个懒腰，面前的笔记本上画满了网格。

坐在旁边的同学探过头来：“克露丝卡尔酱还在研究那个梯度下降问题吗？”

“嗯嗯！我在想，怎么在保证找到最小值的前提下让算法跑得快一点呢？”克露丝卡尔酱歪着头，露出困惑的表情。

“啊，那不就是要求最大学习率吗？不过还要考虑边界情况呢。”同学随口说道。

克露丝卡尔酱眼睛一亮：“对呀！让我们来算算吧～”

问题描述

对于网格标量场 $f$，按以下方式定义 $(i,j)$ 处的离散梯度：

若 $(i,j)$ 位于网格边界，则相应地只计算单侧差分，并且不需要除以 $2$，例如对于 $i=1$ 的点：$\frac{\Delta f}{\Delta x}=f_{i+1,j}-f_{i,j}$。

使用如下的梯度下降算法寻找网格中的最小值：

其中 $\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，否则输出能够找到全局最小值的最大的学习率。

注意：本题中的学习率必须为大于零的偶数。

样例 #1

样例输入 #1

2
2 3 1 3
1 2 2
1 1 2
5 5 1 3
1 2 3 3 2
2 3 2 3 3
3 1 1 2 2
2 3 2 1 3
2 1 1 3 1

样例输出 #1

Impossible
4

提示

对于第一组样例，由于初始位置的梯度为 $0$，因此坐标将永远不变，无法到达取到全局最小值的位置。

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