VUNO is a specialized company that develops Medical AI solutions to assist medical experts in making decisions using artificial intelligence trained on big data and deep learning.

VUNO recently developed a powerful new imaging technique called SP. Using this technique, human tissue is represented as a grid, and each cell in the grid is assigned a single data value that compresses various analysis results of that part. VUNO wants to use this SP imaging technique to study a new antibody called CPCU-1202.

When the CPCU-1202 vaccine is administered to a tissue, an antibody is generated in one of the grid cells. This antibody spreads to adjacent cells (up, down, left, right) that have the same data value as the cell it is currently in. This process is repeated, and when the antibody can no longer spread, it completely permeates the tissue. As a result, the data values of all the cells where the antibody spread are updated to some new, identical value. At this time, by chance, the original data value and the updated data value may be the same.

VUNO's research data consists of pairs of imaging results: one before administering the vaccine to a tissue, and one after administering the vaccine. Given two imaging results, write a program to determine whether the vaccine administered to this tissue could possibly be the CPCU-1202 vaccine.

Figure B.1: CPCU-1202 vaccine administration process. (a) Before administering vaccine, (b) CPCU-1202 administration, (c) Antibody permeating, (d) After administering vaccine

Input

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 30$), representing the size of the SP imaging result. This means the imaging result is a grid of size $N$ rows by $M$ columns.

The next $N$ lines contain the imaging result before administering the vaccine. Each line contains $M$ space-separated integers between $1$ and $1\,000$, inclusive. The $j$-th number in the $i$-th line represents the data value of the cell in the $i$-th row and $j$-th column of the imaging result.

The next $N$ lines contain the imaging result after administering the vaccine, in the same format as above.

Output

If the vaccine administered to the subject could be the CPCU-1202 vaccine, print YES. Otherwise, print NO.

Examples

Input 1

4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
4 4 4 1
4 4 1 3
4 1 3 3
1 3 3 3

Output 1

YES

Input 2

4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3

Output 2

YES

Input 3

4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
2 2 2 1
2 2 2 3
2 1 3 3
1 3 3 3

Output 3

YES

Input 4

4 4
2 2 2 1
2 2 1 2
2 1 2 2
1 2 2 2
3 3 3 1
3 3 1 3
3 1 3 3
1 3 3 3

Output 4

NO

Input 5

3 5
1 1 1 3 3
1 1 2 3 3
1 1 2 2 4
1 1 1 4 4
1 1 2 4 4
1 1 2 2 4

Output 5

YES