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


-----Input-----

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.


-----Output-----

Print a string "Impossible" or "Possible".


-----Examples-----
Input
2 2
2 10
11 5
9 4
3 12

Output
Possible

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

Output
Possible

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

Output
Impossible



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    n, m = read_int_array()
    minm, maxm = [], []
    for _ in range(n):
        minm.append(read_int_array())
    for _ in range(n):
        maxm.append(read_int_array())

    for r in range(n):
        for c in range(m):
            minx = min(minm[r][c], maxm[r][c])
            maxx = max(minm[r][c], maxm[r][c])
            if r:
                if minx <= minm[r-1][c] or maxx <= maxm[r-1][c]:
                    write("Impossible")
                    return
            if c:
                if minx <= minm[r][c-1] or maxx <= maxm[r][c-1]:
                    write("Impossible")
                    return
            minm[r][c] = minx
            maxm[r][c] = maxx
    write("Possible")

main()


def getn():
    return int(input())
def getns():
    return [int(x)for x in input().split()]
# n=getn()
# ns=getns()
n,m=getns()
a=[[0]*m for i in range(n)]
b=[[0]*m for i in range(n)]
a=[]
b=[]
for i in range(n):
    a.append(getns())
for i in range(n):
    b.append(getns())
for i in range(n):
    for j in range(m):
        a[i][j],b[i][j]=min(a[i][j],b[i][j]),max(a[i][j],b[i][j])

def check(x):
    for i in range(n):
        for j in range(m-1):
            if x[i][j]>=x[i][j+1]:
                return False
    for i in range(n-1):
        for j in range(m):
            if x[i][j]>=x[i+1][j]:
                return False
    return True
if check(a) and check(b):
    print('Possible')
else:
    print('Impossible')
quit()


print(a)
print(b)


n, m = map(int, input().split())
l1 = [list(map(int, input().split())) for i in range(n)]
l2 = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
    for j in range(m):
        l1[i][j], l2[i][j] = min(l1[i][j], l2[i][j]), max(l1[i][j], l2[i][j])
ans = True
for i in range(1, n):
    for j in range(m):
        if l1[i][j] <= l1[i - 1][j] or l2[i][j] <= l2[i - 1][j]:
            ans = False
for i in range(n):
    for j in range(1, m):
        if l1[i][j] <= l1[i][j - 1] or l2[i][j] <= l2[i][j - 1]:
            ans = False
if ans:
    print('Possible')
else:
    print('Impossible')

n, m = map(int, input().split())

m1 = [list(map(int, input().split())) for _ in range(n)]
m2 = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
	for j in range(m):
		m1[i][j], m2[i][j] = max(m1[i][j], m2[i][j]), min(m1[i][j], m2[i][j])

def check(matrix):
	return all(all(y > x for x, y in zip(row, row[1:])) for row in matrix)

print("Possible" if check(m1) and check(m2) and check(list(map(list, zip(*m1)))) and check(list(map(list, zip(*m2)))) else "Impossible")

n, m = map(int, input().split())

M1 = []
M2 = []

for i in range(n):
    M1.append(list(map(int, input().split())))
    
for i in range(n):
    M2.append(list(map(int, input().split())))
    
for i in range(n):
    for j in range(m):
        M1[i][j], M2[i][j] = min(M1[i][j], M2[i][j]), max(M1[i][j], M2[i][j])

f = 1        
for i in range(n):
    for j in range(m):
        if i > 0 and (M1[i][j] <= M1[i-1][j] or M2[i][j] <= M2[i-1][j]):
            f = 0
            break
        if j > 0 and (M1[i][j] <= M1[i][j-1] or M2[i][j] <= M2[i][j-1]):
            f = 0
            break
#print(M1)
#print(M2)
if f == 1:
    print("Possible")
else:
    print("Impossible")

n,m=list(map(int, input().split()))
a=[None]*n
b=[None]*n
for i in range(n):
    a[i]=[int(x) for x in input().split()]
for i in range(n):
    b[i]=[int(x) for x in input().split()]
mi=[[None]*m for _ in range(n)]
ma=[[None]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        mi[i][j]=min(a[i][j], b[i][j])
        ma[i][j]=max(a[i][j], b[i][j])

for i in range(n):
    for j in range(m):
        if (i > 0 and mi[i][j] <= mi[i-1][j] or i < n - 1 and mi[i][j] >= mi[i+1][j] or
            j > 0 and mi[i][j] <= mi[i][j-1] or j < m - 1 and mi[i][j] >= mi[i][j+1]):
            print('Impossible')
            raise SystemExit(0)
        if (i > 0 and ma[i][j] <= ma[i-1][j] or i < n - 1 and ma[i][j] >= ma[i+1][j] or
            j > 0 and ma[i][j] <= ma[i][j-1] or j < m - 1 and ma[i][j] >= ma[i][j+1]):
            print('Impossible')
            raise SystemExit(0)

print('Possible')


n, m = list(map(int, input().split()))
a1, a2 = [], []
for i in range(n):
    a1.append(list(map(int, input().split())))
for i in range(n):
    a2.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        a1[i][j], a2[i][j] = min(a1[i][j], a2[i][j]), max(a1[i][j], a2[i][j])

def check(a):
    for i in range(n):
        for j in range(1, m):
            if a[i][j] <= a[i][j-1]: return False
    for j in range(m):
        for i in range(1, n):
            if a[i][j] <= a[i-1][j]: return False
    return True

ans = "Possible" if check(a1) and check(a2) else "Impossible"
print(ans)


def main():
    n, m = map(int, input().split())
    fir = [[] for i in range(n)]
    sec = [[] for i in range(n)]
    for i in range(n):
        fir[i] = list(map(int, input().split()))
    for i in range(n):
        sec[i] = list(map(int, input().split()))
    
    for i in range(n):
        for j in range(m):
            fir[i][j], sec[i][j] = min(fir[i][j], sec[i][j]), max(fir[i][j], sec[i][j])
    
    for i in range(n):
        for j in range(m):
            if i > 0 and fir[i][j] <= fir[i - 1][j]:
                print("Impossible")
                return 0
            if j > 0 and fir[i][j] <= fir[i][j - 1]:
                print("Impossible")
                return 0
            if i > 0 and sec[i][j] <= sec[i - 1][j]:
                print("Impossible")
                return 0
            if j > 0 and sec[i][j] <= sec[i][j - 1]:
                print("Impossible")
                return 0
    print("Possible")
    return 0
            
            
main()

n,m=[int(x) for x in input().split()]
a=[]
b=[]
for i in range(n):
    c=[int(x) for x in input().split()]
    a.append(c)
for i in range(n):
    c=[int(x) for x in input().split()]
    b.append(c)
for i in range(n):
    for j in range(m):
        x,y=a[i][j],b[i][j]
        a[i][j]=min(x,y)
        b[i][j]=max(x,y)
        if j>0:
            if a[i][j]<=a[i][j-1] or b[i][j]<=b[i][j-1]:
                print('Impossible')
                return
        if i>0:
            if a[i][j]<=a[i-1][j] or b[i][j]<=b[i-1][j]:
                print('Impossible')
                return
print('Possible')
            


# -*- coding: utf-8 -*-
# @Time    : 2019/5/5 1:09
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : B. Double Matrix.py


def main():
    n, m = map(int, input().split())
    a, b = [], []
    for i in range(n):
        a.append(list(map(int, input().split())))
    for i in range(n):
        b.append(list(map(int, input().split())))

    def check(mat, i, j):
        if i > 0 and mat[i][j] <= mat[i - 1][j]:
            return False
        if j > 0 and mat[i][j] <= mat[i][j - 1]:
            return False
        return True

    for i in range(n):
        for j in range(m):
            a[i][j], b[i][j] = min(a[i][j], b[i][j]), max(a[i][j], b[i][j])

    for i in range(n):
        for j in range(m):
            if (not check(a, i, j)) or (not check(b, i, j)):
                print('Impossible')
                return
    print('Possible')


def __starting_point():
    main()
__starting_point()

def check(A,H,W):
    for h in range(H):
        for w in range(W-1):
            if A[h][w] >= A[h][w+1]:
                return False
    for w in range(W):
        for h in range(H-1):
            if A[h][w] >= A[h+1][w]:
                return False
    return True

def solve():
    H,W = list(map(int,input().split()))
    A = [list(map(int,input().split())) for i in range(H)]
    B = [list(map(int,input().split())) for i in range(H)]
    if check(A,H,W) and check(B,H,W):
        return 'Possible'
    for h in range(H):
        for w in range(W):
            if A[h][w] > B[h][w]:
                A[h][w], B[h][w] = B[h][w], A[h][w]
    if check(A,H,W) and check(B,H,W):
        return 'Possible'
    return 'Impossible'

print(solve())


n , m = list(map(int,input().split()))
m1 = [list(map(int,input().split())) for i in range(n)]
m2 = [list(map(int,input().split())) for i in range(n)]
import sys
for i in range(n - 1):
	for j in range(m - 1):
		a, b = m1[i][j], m2[i][j]
		c, d = m1[i+1][j], m2[i+1][j]
		e, f = m1[i][j+1], m2[i][j+1]
		if a > b:
			a,b=b,a
		if c>d:
			c,d=d,c
		if e>f:
			e,f=f,e
		if b>=d:
			print("Impossible")
			return
		else:
			if a >=c:
				print("Impossible")
				return
		if b>=f:
			print("Impossible")
			return
		else:
			if a >=e:
				print("Impossible")
				return
for i in range(n-1):
	j = m - 1
	a, b = m1[i][j], m2[i][j]
	c, d = m1[i+1][j], m2[i+1][j]
	if a > b:
		a,b=b,a
	if c>d:
		c,d=d,c
	if b>=d:
			print("Impossible")
			return
	else:
		if a >=c:
			print("Impossible")
			return
for j in range(m-1):
	i = n - 1
	a, b = m1[i][j], m2[i][j]
	e, f = m1[i][j+1], m2[i][j+1]
	if a > b:
		a,b=b,a
	if e>f:
		e,f=f,e
	if b>=f:
			print("Impossible")
			return
	else:
		if a >=e:
			print("Impossible")
			return
print("Possible")

n, m = (int(i) for i in input().split())
L1 = [[int(j) for j in input().split()] for i in range(n)]
L2 = [[int(j) for j in input().split()] for i in range(n)]
for i in range(n):
    for j in range(m):
        if L1[i][j] > L2[i][j]:
            buf = L1[i][j]
            L1[i][j] = L2[i][j]
            L2[i][j] = buf

t = 1
for i in range(n):
    for j in range(m):
        if i > 0:
            if L1[i][j] <= L1[i - 1][j]:
                t = 0
            if L2[i][j] <= L2[i - 1][j]:
                t = 0
        if j > 0:
            if L1[i][j] <= L1[i][j - 1]:
                t = 0
            if L2[i][j] <= L2[i][j - 1]:
                t = 0
if not t:
    print('Impossible')
else:
    print('Possible')


n, m = map(int, input().split())

a = [[0 for _ in range(m)] for _ in range(n)]
b = [[0 for _ in range(m)] for _ in range(n)]


for i in range(n):
	a[i] = list(map(int, input().split()))


for i in range(n):
	b[i] = list(map(int, input().split()))

for i in range(n):
	for j in range(m):
		a[i][j], b[i][j] = min(a[i][j], b[i][j]), max(a[i][j], b[i][j])

# print('a:')
# print(a)

# print('b:')
# print(b)

works = True

for i in range(n):
	for j in range(m-1):
		if a[i][j+1] <= a[i][j]:
			works = False

		if b[i][j+1] <= b[i][j]:
			works = False

for j in range(m):
	for i in range(n-1):
		if a[i+1][j] <= a[i][j]:
			works = False

		if b[i+1][j] <= b[i][j]:
			works = False

if works:
	print('Possible')
else:
	print('Impossible')

import sys
input = sys.stdin.readline

n,m=map(int,input().split())

arr1=[]
for i in range(n):
	arr1.append(list(map(int,input().split())))

arr2=[]
for i in range(n):
	arr2.append(list(map(int,input().split())))
	
arr3=[]
arr4=[]
for i in range(n):
	arr3.append([])
	arr4.append([])
	for j in range(m):
		arr3[i].append(min(arr1[i][j],arr2[i][j]))
		arr4[i].append(max(arr1[i][j],arr2[i][j]))

flag=False
for i in range(n):
	for j in range(m):
		try:
			if arr3[i][j]>=arr3[i][j+1] or arr4[i][j]>=arr4[i][j+1]:
				print("Impossible")
				flag=True
				break
		except:
			pass

		try:
			if arr3[i][j]>=arr3[i+1][j] or arr4[i][j]>=arr4[i+1][j]:
				print("Impossible")
				flag=True
				break
		except:
			pass

	if flag:
		break

if not flag:
	print("Possible")

def isIncreasing(matrix, n, m):
    for j in range(m-1):
        if matrix[0][j+1]<=matrix[0][j]: return False
    for i in range(n-1):
        if matrix[i+1][0]<=matrix[i][0]: return False
    for i in range(1, n):
        for j in range(1, m):
            if matrix[i][j]<=matrix[i-1][j] or matrix[i][j]<=matrix[i][j-1]:
                return False
    return True

n, m = list(map(int, input().split()))
A = []
B = []
for i in range(n):
    A.append(list(map(int, input().split())))
for i in range(n):
    B.append(list(map(int, input().split())))
for i in range(n):
    for j in range(m):
        A[i][j], B[i][j] = min(A[i][j], B[i][j]), max(A[i][j], B[i][j])
if isIncreasing(A, n, m) and isIncreasing(B, n, m): print("Possible")
else: print("Impossible")


import sys

n, m = list(map(int, input().split()))


def read_matrix():
    M = []
    for i in range(n):
        M.append(list(map(int, input().split())))
    return M


A, B = read_matrix(), read_matrix()


for i in range(n):
    for j in range(m):
        A[i][j], B[i][j] = min(A[i][j], B[i][j]), max(A[i][j], B[i][j])
        if i > 0 and (A[i][j] <= A[i-1][j] or B[i][j] <= B[i-1][j]) or \
            j > 0 and (A[i][j] <= A[i][j-1] or B[i][j] <= B[i][j-1]):
            print('Impossible')
            return

print('Possible')


def increasing(m):
    for i in range(len(m)):
        prev = m[i][0]
        for j in range(1, len(m[i])):
            if m[i][j] <= prev: return False
            prev = m[i][j]
    for j in range(len(m[0])):
        prev = m[0][j]
        for i in range(1, len(m)):
            if m[i][j] <= prev: return False
            prev = m[i][j]
    return True

def sol(m1, m2):
    for i in range(len(m1)):
        for j in range(len(m1[i])):
            if m1[i][j] > m2[i][j]:
                m1[i][j], m2[i][j] = m2[i][j], m1[i][j]
    if not increasing(m1) or not increasing(m2): return 'Impossible'
    return 'Possible'
            
def __starting_point():
    [n,m] = [int(x) for x in input().split()]
    m1, m2 = [], []
    for _  in range(n): m1.append([int(x) for x in input().split()])
    for _  in range(n): m2.append([int(x) for x in input().split()])
    print(sol(m1,m2))

__starting_point()

# http://codeforces.com/contest/1162/problem/B
'''
    Author - Subhajit Das
    University of Engineering and Management, Kolkata
    4/5/2019
'''


def main():
    n, m = list(map(int, input().strip().split()))
    a = [list(map(int, input().strip().split())) for _ in range(n)]
    b = [list(map(int, input().strip().split())) for _ in range(n)]

    possible = True

    for row in range(n):
        last_a = a[row][0]
        last_b = b[row][0]
        for col in range(1, m):
            if last_a < a[row][col] and last_b < b[row][col]:
                last_a = a[row][col]
                last_b = b[row][col]
            else:
                a[row][col], b[row][col] = b[row][col], a[row][col]
                if last_a < a[row][col] and last_b < b[row][col]:
                    last_a = a[row][col]
                    last_b = b[row][col]
                else:
                    possible = False
                    break

    if possible:
        for col in range(m):
            last_a = a[0][col]
            last_b = b[0][col]
            for row in range(1, n):
                if last_a < a[row][col] and last_b < b[row][col]:
                    last_a = a[row][col]
                    last_b = b[row][col]
                else:
                    a[row][col], b[row][col] = b[row][col], a[row][col]
                    if last_a < a[row][col] and last_b < b[row][col]:
                        last_a = a[row][col]
                        last_b = b[row][col]
                    else:
                        possible = False
                        break

    print("Possible" if possible else "Impossible")


def __starting_point():
    main()

__starting_point()

def main():
    n, m = list(map(int, input().split()))
    m1 = [[] for _ in range(n)]
    m2 = [[] for _ in range(n)]
    for i in range(n):
        m1[i] = list(map(int, input().split()))
    for i in range(n):
        m2[i] = list(map(int, input().split()))

    for r in range(n):
        for c in range(m):
            m1[r][c], m2[r][c] = min(m1[r][c], m2[r][c]), max(m1[r][c], m2[r][c])

    def checkRow(row):
        for i in range(m-1):
            if m1[row][i] >= m1[row][i+1] or m2[row][i] >= m2[row][i+1]:
                return False
        return True

    def checkCol(col):
        for i in range(n-1):
            if m1[i][col] >= m1[i+1][col] or m2[i][col] >= m2[i+1][col]:
                return False
        return True

    ok = True
    for r in range(n):
        if not checkRow(r):
            ok = False
            break

    if ok:
        for c in range(m):
            if not checkCol(c):
                ok = False
                break

    print('Possible' if ok else 'Impossible')


def __starting_point():
    main()

__starting_point()

import sys
n, m = map(int, input().split())

mat1 = []
mat2 = []

for _ in range(n):
    mat1.append(list(map(int, input().split())))
for _ in range(n):
    mat2.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if mat2[i][j] < mat1[i][j]:
            mat1[i][j], mat2[i][j] = mat2[i][j], mat1[i][j]

for i in range(n):
    for j in range(1, m):
        if mat1[i][j] <= mat1[i][j - 1] or mat2[i][j] <= mat2[i][j - 1]:
            print("Impossible")
            return
for i in range(1, n):
    for j in range(m):
        if mat1[i][j] <= mat1[i - 1][j] or mat2[i][j] <= mat2[i - 1][j]:
            print("Impossible")
            return
print("Possible")