← 返回题目列表

Codeforces · 1162/B

B. 双矩阵

中文机器翻译题面 查看原题

给你两个包含整数的 $$$n \times m$$$ 矩阵。如果接下来的每个数字都大于前一个数字,则整数序列严格递增。如果从左到右的所有数字都严格递增,则该行严格递增。如果从上到下的所有数字都严格递增,则该列严格递增。如果所有行都严格递增并且所有列都严格递增,则矩阵是递增的。

例如,矩阵 $$$\begin{bmatrix} 9&10&11\\ 11&12&14\\ \end{bmatrix}$$$ 正在递增,因为每个单独的行和列都严格递增。另一方面,矩阵 $$$\begin{bmatrix} 1&1\\ 2&3\\ \end{bmatrix}$$$ 没有增加,因为第一行不是严格增加的。

令矩阵中第 $$$i$$$ 行(从顶部)和 $$$j$$$ 第 $$$ 列(从左)的位置表示为 $$$(i, j)$$$。

在一次操作中,您可以选择任意两个数字 $$$i$$$ 和 $$$j$$$,并将第一个矩阵中 $$$(i, j)$$$ 中的数字与第二个矩阵中 $$$(i, j)$$$ 中的数字交换。换句话说,如果两个数字位于相应的位置,则可以交换不同矩阵中的两个数字。

您希望通过执行一定数量的操作(可能没有)来使两个矩阵都增加。确定是否可以这样做。如果是,则打印“可能”,否则,打印“不可能”。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n,m \leq 50$$$) - 每个矩阵的维度。

接下来的 $$$n$$$ 行包含 $$$m$$$ 整数 $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$1 \leq a_{ij} \leq 10^9$$$) - 位于第一个矩阵中 $$$(i, j)$$$ 位置的数字。

接下来的 $$$n$$$ 行包含 $$$m$$$ 整数 $$$b_{i1}, b_{i2}, \ldots, b_{im}$$$ ($$$1 \leq b_{ij} \leq 10^9$$$) - 位于第二个矩阵中 $$$(i, j)$$$ 位置的数字。

输出

打印字符串“不可能”或“可能”。

示例

输入 #1

2 2
2 10
11 5
9 4
3 12

输出 #1

Possible

输入 #2

2 3
2 4 5
4 5 6
3 6 7
8 10 11

输出 #2

Possible

输入 #3

3 2
1 3
2 4
5 10
3 1
3 6
4 8

输出 #3

Impossible

注意

第一个例子,我们可以对矩阵的左上角和右下角的单元格进行操作。生成的矩阵将为 $$$\begin{bmatrix} 9&10\\ 11&12\\ \end{bmatrix}$$$ 和 $$$\begin{bmatrix} 2&4\\ 3&5\\ \end{bmatrix}$$$。

在第二个示例中,我们不需要执行任何操作。

在第三个示例中,无论我们交换什么,我们都无法将两个矩阵中的第一行固定为严格递增。