CF1162B.Double Matrix

You are given two $n \times m$ matrices containing integers. A sequence of integers is strictly increasing if each next number is greater than the previous one. A row is strictly increasing if all numbers from left to right are strictly increasing. A column is strictly increasing if all numbers from top to bottom are strictly increasing. A matrix is increasing if all rows are strictly increasing and all columns are strictly increasing.

For example, the matrix $\begin{bmatrix} 9&10&11\\ 11&12&14\\ \end{bmatrix}$ is increasing because each individual row and column is strictly increasing. On the other hand, the matrix $\begin{bmatrix} 1&1\\ 2&3\\ \end{bmatrix}$ is not increasing because the first row is not strictly increasing.

Let a position in the $i$-th row (from top) and $j$-th column (from left) in a matrix be denoted as $(i, j)$.

In one operation, you can choose any two numbers $i$ and $j$ and swap the number located in $(i, j)$ in the first matrix with the number in $(i, j)$ in the second matrix. In other words, you can swap two numbers in different matrices if they are located in the corresponding positions.

You would like to make both matrices increasing by performing some number of operations (possibly none). Determine if it is possible to do this. If it is, print "Possible", otherwise, print "Impossible".

给你两个 $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)$ 处的数进行交换。换言之，你只能交换两个矩阵中相同位置上的两个数。

你希望经过若干次（可能为零次）上述操作后，使得两个矩阵均为递增矩阵。请判断是否可行。若可行，输出 "Possible"；否则，输出 "Impossible"。

The first line contains two integers $n$ and $m$ ($1 \leq n,m \leq 50$) — the dimensions of each matrix.

Each of the next $n$ lines contains $m$ integers $a_{i1}, a_{i2}, \ldots, a_{im}$ ($1 \leq a_{ij} \leq 10^9$) — the number located in position $(i, j)$ in the first matrix.

Each of the next $n$ lines contains $m$ integers $b_{i1}, b_{i2}, \ldots, b_{im}$ ($1 \leq b_{ij} \leq 10^9$) — the number located in position $(i, j)$ in the second matrix.

第一行包含两个整数 $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)$ 处的数值。

Print a string "Impossible" or "Possible".

打印字符串“Impossible”或“Possible”。

The first example, we can do an operation on the top left and bottom right cells of the matrices. The resulting matrices will be $\begin{bmatrix} 9&10\\ 11&12\\ \end{bmatrix}$ and $\begin{bmatrix} 2&4\\ 3&5\\ \end{bmatrix}$.

In the second example, we don't need to do any operations.

In the third example, no matter what we swap, we can't fix the first row to be strictly increasing in both matrices.

第一个例子中，我们可以对两个矩阵的左上角和右下角单元格执行一次操作。操作后得到的矩阵分别为 $\begin{bmatrix} 9&10\\ 11&12\\ \end{bmatrix}$ 和 $\begin{bmatrix} 2&4\\ 3&5\\ \end{bmatrix}$。

第二个例子中，我们无需执行任何操作。

第三个例子中，无论怎样交换，我们都无法使两个矩阵的第一行同时严格递增。