Cutting the Board

View as PDF

Submit solution


Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

After 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~.

image

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~

image

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

Please read the guidelines before commenting.



  • 0
    Boss  commented on July 5, 2025, 4:16 a.m.

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


  • -5
    hoangquan2509  commented on July 4, 2025, 3:54 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.