Nastya came to her informatics lesson, and her teacher who is, by the way, a little bit famous here gave her the following task.

Two matrices $A$ and $B$ are given, each of them has size $n \times m$. Nastya can perform the following operation to matrix $A$ unlimited number of times:   take any square square submatrix of $A$ and transpose it (i.e. the element of the submatrix which was in the $i$-th row and $j$-th column of the submatrix will be in the $j$-th row and $i$-th column after transposing, and the transposed submatrix itself will keep its place in the matrix $A$). 

Nastya's task is to check whether it is possible to transform the matrix $A$ to the matrix $B$.

 $\left. \begin{array}{|c|c|c|c|c|c|c|c|} \hline 6 & {3} & {2} & {11} \\ \hline 5 & {9} & {4} & {2} \\ \hline 3 & {3} & {3} & {3} \\ \hline 4 & {8} & {2} & {2} \\ \hline 7 & {8} & {6} & {4} \\ \hline \end{array} \right.$ Example of the operation 

As it may require a lot of operations, you are asked to answer this question for Nastya.

A square submatrix of matrix $M$ is a matrix which consist of all elements which comes from one of the rows with indeces $x, x+1, \dots, x+k-1$ of matrix $M$ and comes from one of the columns with indeces $y, y+1, \dots, y+k-1$ of matrix $M$. $k$ is the size of square submatrix. In other words, square submatrix is the set of elements of source matrix which form a solid square (i.e. without holes).


-----Input-----

The first line contains two integers $n$ and $m$ separated by space ($1 \leq n, m \leq 500$) — the numbers of rows and columns in $A$ and $B$ respectively.

Each of the next $n$ lines contains $m$ integers, the $j$-th number in the $i$-th of these lines denotes the $j$-th element of the $i$-th row of the matrix $A$ ($1 \leq A_{ij} \leq 10^{9}$).

Each of the next $n$ lines contains $m$ integers, the $j$-th number in the $i$-th of these lines denotes the $j$-th element of the $i$-th row of the matrix $B$ ($1 \leq B_{ij} \leq 10^{9}$).


-----Output-----

Print "YES" (without quotes) if it is possible to transform $A$ to $B$ and "NO" (without quotes) otherwise.

You can print each letter in any case (upper or lower).


-----Examples-----
Input
2 2
1 1
6 1
1 6
1 1

Output
YES
Input
2 2
4 4
4 5
5 4
4 4

Output
NO
Input
3 3
1 2 3
4 5 6
7 8 9
1 4 7
2 5 6
3 8 9

Output
YES


-----Note-----

Consider the third example. The matrix $A$ initially looks as follows.

$$ \begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{bmatrix} $$

Then we choose the whole matrix as transposed submatrix and it becomes

$$ \begin{bmatrix} 1 & 4 & 7\\ 2 & 5 & 8\\ 3 & 6 & 9 \end{bmatrix} $$

Then we transpose the submatrix with corners in cells $(2, 2)$ and $(3, 3)$. 

$$ \begin{bmatrix} 1 & 4 & 7\\ 2 & \textbf{5} & \textbf{8}\\ 3 & \textbf{6} & \textbf{9} \end{bmatrix} $$

So matrix becomes

$$ \begin{bmatrix} 1 & 4 & 7\\ 2 & 5 & 6\\ 3 & 8 & 9 \end{bmatrix} $$

and it is $B$.

Difficulty: interview

Starter code:

Solutions:
from collections import Counter


def input_matrix():
    res = tuple((Counter() for _ in range(n + m)))
    for i in range(n):
        for j, a in enumerate(map(int, input().split())):
            res[i + j][a] += 1
    return res


n, m = list(map(int, input().split()))
if input_matrix() == input_matrix():
    print("YES")
else:
    print("NO")


# -*- coding: utf-8 -*-

from collections import defaultdict


def rli():
    return list(map(int, input().split()))


def main():
    n, m = rli()
    cnt = [defaultdict(int) for i in range(n + m + 10)]
    for i in range(n):
        nums = rli()
        for j in range(m):
            cnt[i + j][nums[j]] += 1
    for i in range(n):
        nums = rli()
        for j in range(m):
            cnt[i + j][nums[j]] -= 1
    for i in range(n + m + 10):
        for v in list(cnt[i].values()):
            if v != 0:
                print('NO')
                return
    print('YES')


def __starting_point():
    main()

__starting_point()

n,m = map(int,input().split())
# rows and columns
# max 500

from collections import defaultdict
diag_a = defaultdict(list)
diag_b = defaultdict(list)

for x in range(n):
    for i,val in enumerate(list(map(int,input().split()))):
        diag_a[x+i].append(val)

for x in range(n):
    for i,val in enumerate(list(map(int,input().split()))):
        diag_b[x+i].append(val)

diag_a = {k:sorted(v) for k,v in diag_a.items()}
diag_b = {k:sorted(v) for k,v in diag_b.items()}
for k in diag_a.keys():
    if diag_a[k] != diag_b[k]:
        print ("NO")
        return
print ("YES")

ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())

n, m = mi()
a = [li() for i in range(n)]
b = [li() for i in range(n)]
p = [[] for i in range(n + m)]
q = [[] for i in range(n + m)]
for i in range(n):
    for j in range(m):
        p[i + j].append(a[i][j])
        q[i + j].append(b[i][j])
print('YES' if all(sorted(x) == sorted(y) for x, y in zip(p, q)) else 'NO')

import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

n, m = mints()
z = [None,None]
for k in range(2):
	x = [[] for i in range(n+m)]
	for i in range(n):
		a = list(mints())
		for j in range(m):
			x[i+j].append(a[j])
	z[k] = x
for i in range(n+m):
	a = z[0][i]
	b = z[1][i]
	a.sort()
	b.sort()
	if a != b:
		print("NO")
		return
print("YES")


N, M = list(map(int, input().split()))
A = [[int(a) for a in input().split()] for _ in range(N)]
B = [[int(a) for a in input().split()] for _ in range(N)]

AA = [[] for _ in range(N+M-1)]
BB = [[] for _ in range(N+M-1)]

for n in range(N):
    for m in range(M):
        AA[n+m].append(A[n][m])
        BB[n+m].append(B[n][m])

for i in range(N+M-1):
    AA[i] = sorted(AA[i])
    BB[i] = sorted(BB[i])
    if AA[i] != BB[i]:
        print("NO")
        break
else:
    print("YES")


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

b1 = []
for i in range(n):
    b1.append(input().split())

b2 = []
for i in range(n):
    b2.append(input().split())

def works(n, m, b1, b2):
    for diag in range(n + m - 1):
        l1 = []
        l2 = []
        for col in range(diag + 1):
            point = [col, diag-col]
            if 0 <= point[0] < n and 0 <= point[1] < m:
                l1.append(b1[point[0]][point[1]])
                l2.append(b2[point[0]][point[1]])
        if sorted(l1) != sorted(l2):
            return False
    return True

if works(n, m, b1, b2):
    print('YES')
else:
    print('NO')


# import getpass
# import math
# import sys
# import string
# import re
# import math
# import random
# from decimal import Decimal, getcontext


def ria():
    return [int(i) for i in input().split()]


# if getpass.getuser() != 'frohenk':
#     filename = 'half'
#     # sys.stdin = open('input.txt')
#     # sys.stdout = open('output.txt', 'w')
# else:
#     sys.stdin = open('input.txt')
#     # sys.stdin.close()

h, w = ria()

mt1 = []
mt2 = []

for y in range(h):
    mt1.append(ria())
for y in range(h):
    mt2.append(ria())
# now its y then x

# print(mt1, mt2)

for x in range(w):
    st1 = []
    st2 = []

    y = 0
    while w > x >= 0 and h > y >= 0:
        st1.append(mt1[y][x])
        st2.append(mt2[y][x])
        x -= 1
        y += 1

    st1.sort()
    st2.sort()
    if st1 != st2:
        print('NO')
        return

for y in range(h):
    st1 = []
    st2 = []

    x = w - 1
    while w > x >= 0 and h > y >= 0:
        st1.append(mt1[y][x])
        st2.append(mt2[y][x])
        x -= 1
        y += 1
    # print(st1)
    # print(st2)
    #
    st1.sort()
    st2.sort()
    if st1 != st2:
        print('NO')
        return
print('YES')

'''input
3 3
1 2 3
4 5 6
7 8 9
1 4 7
2 5 6
3 8 9
'''
import sys
from collections import defaultdict as dd
from itertools import  permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
import heapq
mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())

n,m=ri()

mat=[]
mat1=[]
for i in range(n):
	mat.append(ri())
for i in range(n):
	mat1.append(ri())
one=dd(list)
for i in range(n):
	for j in range(m):
		one[i+j].append(mat[i][j])

two=dd(list)
for i in range(n):
	for j in range(m):
		two[i+j].append(mat1[i][j])

for i in one:
	one[i].sort()
for i in two:
	two[i].sort()

f=1
for i in one:
	if one[i]!=two[i]:
		f=0
if f:
	print("YES")
else:
	print("NO")

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 j in range(m + n - 1):
	x1 = {}
	x2 = {}
	for i in range(j + 1):
		if j - i < n and i < m:
			x1[m1[j-i][i]] = 0
			x2[m2[j-i][i]] = 0
	for i in range(j + 1):
		if j - i < n and i < m:
			x1[m1[j-i][i]] += 1
			x2[m2[j-i][i]] += 1
	if x1 != x2:
		print("NO")
		return
print("YES")

n, m = map(int, input().split())
m1 = []
m2 = []
for i in range(n):
    m1.append([int(j) for j in input().split()])
for i in range(n):
    m2.append([int(j) for j in input().split()])
d1 = [[] for i in range(n + m - 1)]
d2 = [[] for i in range(n + m - 1)]
for i in range(n):
    for j in range(m):
        d1[i + j].append(m1[i][j])
        d2[i + j].append(m2[i][j])
flag = True
for i in range(n + m - 1):
    d1[i].sort()
    d2[i].sort()
    if d1[i][::] != d2[i][::]:
        flag = False
if flag:
    print("YES")
else:
    print("NO")

n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(n)]
l1, l2 = [[] for i in range(n + m)], [[] for i in range(n + m)]
for i in range(n):
    for j in range(m):
        l1[i + j].append(a[i][j])
        l2[i + j].append(b[i][j])
for i in l1:
    i.sort()
for i in l2:
    i.sort()
print('YES' if l1 == l2 else 'NO')


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

ok = 'YES'
for i in range(m - 1 + n - 1 + 1):
    d = dict()
    for x in range(min(i + 1, m)):
        if i - x < n:
            if a[i - x][x] in d:
                d[a[i - x][x]] += 1
            else:
                d[a[i - x][x]] = 1
    for x in range(min(i + 1, m)):
        if i - x < n:
            if b[i - x][x] in d:
                d[b[i - x][x]] -= 1
                if d[b[i - x][x]] == 0:
                    d.__delitem__(b[i - x][x])
            else:
                print('NO')
                return
print('YES')


# -*- coding: utf-8 -*-
# @Time    : 2019/3/12 1:05
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Nastya Is Transposing Matrices.py

from collections import defaultdict

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

    dict1 = defaultdict(list)
    for i in range(n):
        for j in range(m):
            dict1[i + j].append(a[i][j])

    dict2 = defaultdict(list)
    for i in range(n):
        for j in range(m):
            dict2[i + j].append(b[i][j])
    # print(dict1)
    # print(dict2)

    for i in range(n + m - 1):
        if sorted(dict1[i]) != sorted(dict2[i]):
            print('NO')
            return
    print('YES')


def __starting_point():
    main()

__starting_point()

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(n)]
aa = [[] for _ in range(n+m)]
bb = [[] for _ in range(n+m)]
for i in range(n):
    for k in range(m):
        aa[i+k].append(a[i][k])        
        bb[i+k].append(b[i][k])
print("YES" if all(map(lambda x, y: sorted(x) == sorted(y), aa, bb)) else "NO")

from collections import defaultdict

n, m = (int(t) for t in input().split(' '))
m1 = [[int(t) for t in input().split(' ')] for _ in range(n)]
m2 = [[int(t) for t in input().split(' ')] for _ in range(n)]

def get_csum(mx):
    csum = [defaultdict(int) for _ in range(n+m+1)]
    for i in range(n):
        for j in range(m):
            csum[i+j][mx[i][j]] += 1
    return csum

csum1 = get_csum(m1)
csum2 = get_csum(m2)
print('YES' if csum1 == csum2 else 'NO')


n,m = [int(x) for x in input().split()]

A = []

B = []

for _ in range(n):
    A.append([int(x) for x in input().split()])

for _ in range(n):
    B.append([int(x) for x in input().split()])

AD = []
BD = []
for s in range(2,m+n+1):
    at = []
    bt = []
    for r in range(1,n+1):
        c = s-r
        if 1 <= c and c <= m:
            at.append(A[r-1][c-1])
            bt.append(B[r-1][c-1])
    at.sort()
    bt.sort()
    AD.append(at)
    BD.append(bt)
    
if AD == BD:
    print('YES')

else:
    print('NO')

n,m=[int(x) for x in input().split()]
A=[]
B=[]
for i in range(n):
    a=[int(x) for x in input().split()]
    A.append(a)
for i in range(n):
    a=[int(x) for x in input().split()]
    B.append(a)
a_list=[]
for i in range(n):
    a=[]
    j=0
    a.append(A[i][j])
    while 1:
        if i-1>=0 and j+1<=m-1:
            i-=1
            j+=1
            a.append(A[i][j])
        else:
            break
    a_list.append(a)
i=n-1
for j in range(1,m):
    i=n-1
    a=[]
    a.append(A[i][j])
    while 1:
        if i-1>=0 and j+1<=m-1:
            i-=1
            j+=1
            a.append(A[i][j])
        else:
            break
    a_list.append(a)
    
b_list=[]
for i in range(n):
    a=[]
    j=0
    a.append(B[i][j])
    while 1:
        if i-1>=0 and j+1<=m-1:
            i-=1
            j+=1
            a.append(B[i][j])
        else:
            break
    b_list.append(a)
i=n-1
for j in range(1,m):
    a=[]
    i=n-1
    a.append(B[i][j])
    while 1:
        if i-1>=0 and j+1<=m-1:
            i-=1
            j+=1
            a.append(B[i][j])
        else:
            break
    b_list.append(a)
for i in range(len(a_list)):
    a=sorted(a_list[i])
    b=sorted(b_list[i])
    if a!=b:
        print('NO')
        break
else:
    print('YES')


n,m=list(map(int,input().split()))
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))
b=[]
flag=True
for i in range(n):
    b.append(list(map(int,input().split())))
for i in range(m+n-1):
    cur=[]
    curb=[]
    for l in range(i+1):
        try:
            cur.append(a[i-l][l])
            curb.append(b[i-l][l])
        except:
            pass
    cur.sort()
    curb.sort()
    if cur!=curb:
        flag=False
if flag:
    print('YES')
else:
    print('NO')


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

flag=0
for i in range(n):
	temparr1=[]
	temparr2=[]
	indexi=i
	indexj=0
	while(indexi>=0 and indexj<m):
		temparr1.append(arr1[indexi][indexj])
		temparr2.append(arr2[indexi][indexj])
		indexi-=1
		indexj+=1
	temparr1.sort()
	temparr2.sort()
	#print(*temparr1)
	#print(*temparr2)
	for j in range(len(temparr1)):
		if(temparr1[j]!=temparr2[j]):
			flag=1
			break
if(flag==1):
	print('NO')
else:
	for i in range(1,m):
		temparr1=[]
		temparr2=[]
		indexi=n-1
		indexj=i
		while(indexi>=0 and indexj<m):
			temparr1.append(arr1[indexi][indexj])
			temparr2.append(arr2[indexi][indexj])
			indexi-=1
			indexj+=1
		temparr1.sort()
		temparr2.sort()
		#print(*temparr1)
		for j in range(len(temparr1)):
			if(temparr1[j]!=temparr2[j]):
				flag=1
				break
	if(flag==0):
		print('YES')
	else:
		print('NO')


n, m = map(int, input().split())
mat1 = [[0 for i in range(m)] for j in range(n)]
mat2 = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    mat1[i] = list(map(int, input().split()))
for i in range(n):
    mat2[i] = list(map(int, input().split()))
l1 = [dict() for i in range(n + m - 1)]
l2 = [dict() for i in range(n + m - 1)]
for i in range(n):
    for j in range(m):
        if mat1[i][j] in l1[i + j]:
            l1[i + j][mat1[i][j]] += 1
        else:
            l1[i + j][mat1[i][j]] = 1
        if mat2[i][j] in l2[i + j]:
            l2[i + j][mat2[i][j]] += 1
        else:
            l2[i + j][mat2[i][j]] = 1
flag = 0
for i in range(n + m - 1):
    if l1[i] != l2[i]:
        flag = 1
print(flag * "NO" + (1 - flag) * "YES")

n , m = list(map(int,input().split()))
a , b = [] , []
for _ in range(n):
    aux = [int(x) for x in input().split()]
    a.append(aux)
for _ in range(n):
    aux = [int(x) for x in input().split()]
    b.append(aux)

def diagonalOrder(a,b):
    for line in range(1,n+m):
        start_col = max(0,line-n)
        count = min(line,(m-start_col),n)
        aux_a = []
        aux_b = []
        for j in range(count):
            aux_a.append(a[min(n,line)-j-1][start_col+j])
            aux_b.append(b[min(n,line)-j-1][start_col+j])
        if(sorted(aux_a)!=sorted(aux_b)): return("NO")
    return("YES")


print(diagonalOrder(a,b))


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

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

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

for i in range(m + n -1):
    d1 = {}
    d2 ={}

    for j in range(n):
        l = j
        r = i - j
        if l >=0 and l < n and r >= 0 and r < m:
            e = a[l][r]
            if e not in d1:
                d1[e] = 0
            d1[e] += 1

    for j in range(n):
        l = j
        r = i - j
        if l >= 0 and l < n and r >= 0 and r < m:
            e = b[l][r]
            if e not in d2:
                d2[e] = 0
            d2[e] += 1

    for k in d1:
        if k not in d2:
            print('NO')
            return
        if d1[k] != d2[k]:
            print('NO')
            return
print('YES')


n,m = list(map(int, input().strip().split()))
a = []
b = []
for i in range(n):
    l = list(map(int, input().strip().split()))
    a.append(l)
for i in range(n):
    l = list(map(int, input().strip().split()))
    b.append(l)
test = True
for i in range(n+m-1):
    c = []
    d = []
    if i < m-1:
        for j in range(i,-1,-1):
            c.append(a[i-j][j])
            d.append(b[i-j][j])
            if i-j == n-1:
                break
        c.sort()
        d.sort()
        if c!= d:
            test = False
            break
    else:
        x = i- (m-1)
        for j in range(x,n):
            c.append(a[j][m-1-(j-x)])
            d.append(b[j][m-1-(j-x)])
            if m-1-(j-x) == 0:
                break
        c.sort()
        d.sort()
        if c!= d:
            test = False
            break
if test == True:
    print('YES')
else:
    print('NO')


def main():
    n, m = map(int, input().split())

    a = [[] for i in range(n)]
    b = [[] for i in range(n)]
    aDicts = [dict() for i in range(n + m - 1)]
    bDicts = [dict() for i in range(n + m - 1)]    
    
    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):
            if a[i][j] in aDicts[i + j].keys():
                aDicts[i + j][a[i][j]] += 1
            else:
                aDicts[i + j][a[i][j]] = 1
    
            if b[i][j] in bDicts[i + j].keys():
                bDicts[i + j][b[i][j]] += 1
            else:
                bDicts[i + j][b[i][j]] = 1            

    for i in range(n + m - 1):
        if aDicts[i] != bDicts[i]:
            print("NO")
            return 0
    print("YES")
    return 0

main()