## DMOPC '22 Contest 4 P2 - Fake Painting

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

In the th century, Picasso used an unconventional painting technique to create his art. Initially, he started with a canvas that can be represented by an by grid of integers. Let denote the position of the cell in the -th row from the top and -th column from the left.

Picasso painted the canvas using a special type of brushstroke, which he used an unknown (possibly zero) number of times. Each brushstroke consisted of the following: First, he chose a nonzero integer and a position . Then, he added to cell , flipped the grid either horizontally or vertically, and added to cell again.

Specifically, a horizontal flip reverses the order of the columns, while a vertical flip reverses the order of the rows.

You want to buy one of Picasso's masterpieces, however, it could be a fake. Given the original canvas and a potential canvas , determine if could have been created by Picasso.

#### Input Specification

The first line contains space-separated integers and .

The next lines contain space-separated integers representing the cells of the original canvas.

The last lines contain space-separated integers representing the cells of the potential canvas.

#### Output Specification

Output YES if could have been created by Picasso, and NO otherwise.

#### Sample Input 1

2 2
1 2
3 5
2 1
4 2

#### Sample Output 1

YES

#### Explanation for Sample 1

Picasso can perform brushstroke to transform into : choose as , add to , flip the grid horizontally, and add to again.

#### Sample Input 2

2 2
1 2
3 5
1 2
3 6

#### Sample Output 2

NO

#### Explanation for Sample 2

No sequence of moves can be performed which transforms to .

#### Sample Input 3

1 3
2 3 2
1 2 2

#### Sample Output 3

NO

#### Explanation for Sample 3

No sequence of moves can be performed which transforms to .