Cutting the Board
View as PDFAfter an incident during the first-class sorcerer examination, the Continental Magic Association decided to permanently eliminate this exam and replace it with a similar one that requires both magical abilities and mathematical thinking from the candidates. The exam is described as follows:
There will be two matrices ~a~ and ~b~, each consisting of ~n~ rows and ~m~ columns drawn by magic. The rows are numbered from ~1~ to ~n~ from top to bottom, and the columns are numbered from ~1~ to ~m~ from left to right.
During the exam, candidates can use magic to perform transformations on matrix ~a~ of one of two types (any number of times and in any order):
Vertical flip: Choose a cut between columns ~y~ and ~y+1~ (~1 \le y < m~). Divide the grid into left and right halves, swap them, and merge back together. After this, column ~j \le y~ becomes ~j + (m - y)~, and column ~j > y~ becomes ~j - y~.
Horizontal flip: Choose a cut between rows ~x~ and ~x+1~ (~1 \le x < n~). Divide the grid into top and bottom halves, swap them, and merge back together. After this, row ~i \le x~ becomes ~i + (n - x)~, and row ~i > x~ becomes ~i - x~.
Illustration of the two types of matrix transformations
To complete the exam, candidates need to transform matrix ~a~ into matrix ~b~ using only the two types of transformations described above.
Please help the candidates determine whether there is a way to complete the exam.
Input
Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 50~). The description of each test case is as follows.
The first line contains two integers ~n~ and ~m~ (~1 \le n, m \le 50~) – the dimensions of the two matrices.
The ~i~-th line in the next ~n~ lines contains ~m~ integers ~a_{i,1}, a_{i,2}, \ldots, a_{i,m}~ (~1 \le a_{i,j} \le 10^4~) – the numbers in the ~i~-th row of matrix ~a~.
The ~i~-th line in the next ~n~ lines contains ~m~ integers ~b_{i,1}, b_{i,2}, \ldots, b_{i,m}~ (~1 \le b_{i,j} \le 10^4~) – the numbers in the ~i~-th row of matrix ~b~.
It is guaranteed that:
The total value of ~n~ across all test cases does not exceed ~50~.
The total value of ~m~ across all test cases does not exceed ~50~.
Output
For each test case, if there exists a way to transform the matrix as required by the problem statement, print YES. Otherwise, print NO.
Scoring
The total score for this problem is ~500~.
Sample Input 1
2
3 4
1 2 5 2
5 7 4 6
2 3 1 3
3 2 3 1
2 1 2 5
6 5 7 4
2 2
1 1
1 1
1 1
2 2
Sample Output 1
YES
NO
Notes
In the first example, there exists a way to transform the matrix as follows:
Vertical flip with the cut between column ~1~ and column ~2~
Horizontal flip with the cut between row ~2~ and row ~3~
Vertical flip with the cut between column ~2~ and column ~3~
Illustration of example 1
In the second example, no matter what transformation is performed, matrix ~a~ will remain unchanged; thus, there is no way to transform matrix ~a~ into matrix ~b~.
Comments
Tôi tin chắc là chỉ có Frieren mới giải được bài này :))) Còn người ra đề chắc là Serie á.
This comment is hidden due to too much negative feedback. Show it anyway.