Double Matrix

题意翻译

【问题描述】 如果矩阵每行从左到右的所有数字严格递增，则称行严格递增，如果从上到下的所有数字都严格递增，则列严格递增。如果所有行和列都严格递增，则称矩阵为递增矩阵。 给出两个包含整数的n×m矩阵A和B，你可以尝交换A_ij和B_ij的值（即交换A、B矩阵同一位置的值）使矩阵A和B变成递增矩阵。 【输入格式】 第一行包含两个整数n和m（1≤n，m≤50）表示每个矩阵的行数和列数。 接下来n行表示A矩阵，每行m个数（A_i1、A_i2…A_im）（1≤A_ij 1≤10^9）。 接下来n行表示B矩阵，每行m个数（B_i1、B_i2…B_im）(1≤A_ij 1≤10^9)。 【输出格式】 如果能使用A、B变成递增矩阵的，输出Possible，否则输出Impossible。

题目描述

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".

输入输出格式

输入格式

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.

输出格式

Print a string "Impossible" or "Possible".

输入输出样例

输入样例 #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

说明

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.