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.
Constraints
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
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
.
Comments