Problem Description

Two infinite hexagonal grids are given. On each grid, some lattice points are black and some are white, as shown in the figure below.

:::align{center} :::

We use a 3D coordinate $(x,y,z)\ (x,y,z\in\mathbb{Z},x+y+z=0)$ to describe each lattice point in the grid, as shown below.

:::align{center} :::

We can perform the following flip operation as shown below. Each time, choose a 3D coordinate $(x,y,z)\ (x,y,z\in\mathbb{Z},x+y+z=0)$, and flip the colors (black to white, white to black) of the ring of lattice points around it. That is, flip the colors of lattice points $(x,y-1,z+1)$, $(x+1,y-1,z)$, $(x+1,y,z-1)$, $(x,y+1,z-1)$, $(x-1,y+1,z)$, $(x-1,y,z+1)$.

:::align{center} :::

Determine whether it is possible to perform some number of flip operations on the first hexagonal grid so that the color at every lattice point becomes the same as in the second hexagonal grid.

Input Format

The first line contains an integer $T$ ($1 \le T \le 100$), representing the number of testdata groups.

Then the testdata are given one by one. For each testdata group:

The first line contains two integers $n,m$ ($0 \le n, m \le 10^5$), representing the numbers of black lattice points on the two hexagonal grids, respectively.

The next $n$ lines: the $i$-th line contains three integers $x_i,y_i,z_i$ ($-10^9 \le x_i, y_i, w_i \le 10^9, x_i + y_i + z_i = 0$), representing the coordinates of the $i$-th black point on the first hexagonal grid.

The next $m$ lines: the $i$-th line contains three integers $u_i,v_i,w_i$ ($-10^9 \le u_i,v_i,w_i \le 10^9, u_i+v_i+w_i = 0$), representing the coordinates of the $i$-th black point on the second hexagonal grid.

It is guaranteed that $\sum n\le 2 \times 10^5,\sum m\le 2 \times 10^5$ over all testdata.

Output Format

For each testdata group, output YES if the first hexagonal grid can be transformed by some number of flip operations so that the color at every lattice point matches the second hexagonal grid; otherwise output NO. You may output the answer in any letter case, for example, yEs, yes, Yes, and YES are all accepted as a positive answer.

1
9 7
0 2 -2
-2 2 0
0 1 -1
2 0 -2
-1 0 1
2 -2 0
0 -2 2
0 0 0
-2 1 1
-1 1 0
1 1 -2
2 0 -2
2 -1 -1
0 -1 1
0 -2 2
1 -2 1

YES

2
5 3
0 0 0
-1 1 0
-1 0 1
0 -1 1
1 0 -1
0 0 0
0 1 -1
1 -1 0
4 3
-1 1 0
-1 0 1
0 -1 1
1 0 -1
0 0 0
0 1 -1
1 -1 0

YES
NO

Hint

In Sample $1$, the two lattice-point diagrams are exactly the two diagrams in the top image.

Translated by ChatGPT 5