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×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\).
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,…,x+k−1\) of matrix \(M\) and comes from one of the columns with indeces \(y,y+1,…,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≤n,m≤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≤Aij≤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≤Bij≤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).
思路：这个题看着非常的yinjian，因为如果你不手动模拟一下的话，这个题应该是没有什么思路的。那么如果你手画一下，就会发现，一个方格，只能和与它处于同一副对角线上的方格互换，并且可以随意互换。有了这个思路，我们可以用map之类的东西轻松维护。（注：位于同一主对角线的两个方格\((X_1,Y_1)\)和\((X_2,Y_2)\)，满足\(X_1 - Y_1 = X_2 - Y_2\)；位于同一副对角线的两个方格\((X_1,Y_1)\)和\((X_2,Y_2)\)，满足\(X_1 + Y_1 = X_2 + Y_2\)。）
#include <bits/stdc++.h>
using namespace std;
map <int, int> mp[1005];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, x; i <= n; i++) for (int j = 1; j <= m; j++)
{
scanf("%d", &x);
++mp[i + j][x];
}
for (int i = 1, x; i <= n; i++) for (int j = 1; j <= m; j++)
{
scanf("%d", &x);
if (--mp[i + j][x] < 0) return puts("NO"), 0;
} puts("YES");
}