310510: CF1844E. Great Grids

E. Great Gridstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

An $n \times m$ grid of characters is called great if it satisfies these three conditions:

• Each character is either 'A', 'B', or 'C'.
• Every $2 \times 2$ contiguous subgrid contains all three different letters.
• Any two cells that share a common edge contain different letters.

Let $(x,y)$ denote the cell in the $x$-th row from the top and $y$-th column from the left.

You want to construct a great grid that satisfies $k$ constraints. Each constraint consists of two cells, $(x_{i,1},y_{i,1})$ and $(x_{i,2},y_{i,2})$, that share exactly one corner. You want your great grid to have the same letter in cells $(x_{i,1},y_{i,1})$ and $(x_{i,2},y_{i,2})$.

Determine whether there exists a great grid satisfying all the constraints.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains three integers, $n$, $m$, and $k$ ($2 \le n,m \le 2 \cdot 10^3$, $1 \le k \le 4 \cdot 10^3$).

Each of the next $k$ lines contains four integers, $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, and $y_{i,2}$ ($1 \le x_{i,1} < x_{i,2} \le n$, $1 \le y_{i,1},y_{i,2} \le m$). It is guaranteed that either $(x_{i,2},y_{i,2}) = (x_{i,1}+1,y_{i,1}+1)$ or $(x_{i,2},y_{i,2}) = (x_{i,1}+1,y_{i,1}-1)$.

The pairs of cells are pairwise distinct, i.e. for all $1 \le i < j \le k$, it is not true that $x_{i,1} = x_{j,1}$, $y_{i,1} = y_{j,1}$, $x_{i,2} = x_{j,2}$, and $y_{i,2} = y_{j,2}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^3$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^3$.

It is guaranteed that the sum of $k$ over all test cases does not exceed $4 \cdot 10^3$.

Output

For each test case, output "YES" if a great grid satisfying all the constraints exists and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

ExampleInput

4
3 4 4
1 1 2 2
2 1 3 2
1 4 2 3
2 3 3 2
2 7 2
1 1 2 2
1 2 2 1
8 5 4
1 2 2 1
1 5 2 4
7 1 8 2
7 4 8 5
8 5 4
1 2 2 1
1 5 2 4
7 1 8 2
7 5 8 4

Output

YES
NO
YES
NO

Note

In the first test case, the following great grid satisfies all the constraints:

B	A	B	C
C	B	C	A
A	C	A	B

In the second test case, the two constraints imply that cells $(1,1)$ and $(2,2)$ have the same letter and cells $(1,2)$ and $(2,1)$ have the same letter, which makes it impossible for the only $2 \times 2$ subgrid to contain all three different letters.

题目大意：
一个 $n \times m$ 的字符网格被称为“great”，如果它满足以下三个条件：
1. 每个字符都是 'A'、'B' 或 'C' 之一。
2. 每个连续的 $2 \times 2$ 子网格都包含这三个不同的字母。
3. 任何共享公共边的两个单元格都包含不同的字母。

给定 $k$ 个约束，每个约束由两个共享一个角的单元格组成，需要构造一个满足所有约束的“great”网格。

输入输出数据格式：
输入：
- 第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。
- 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n, m \le 2 \cdot 10^3$，$1 \le k \le 4 \cdot 10^3$）。
- 接下来的 $k$ 行，每行包含四个整数 $x_{i,1}$、$y_{i,1}$、$x_{i,2}$ 和 $y_{i,2}$（$1 \le x_{i,1} < x_{i,2} \le n$，$1 \le y_{i,1}, y_{i,2} \le m$），表示约束。保证 $(x_{i,2}, y_{i,2}) = (x_{i,1}+1, y_{i,1}+1)$ 或 $(x_{i,2}, y_{i,2}) = (x_{i,1}+1, y_{i,1}-1)$。
- 确保所有测试用例的 $n$ 之和不超过 $2 \cdot 10^3$，$m$ 之和不超过 $2 \cdot 10^3$，$k$ 之和不超过 $4 \cdot 10^3$。

输出：
- 对于每个测试用例，如果存在满足所有约束的“great”网格，输出 "YES"，否则输出 "NO"。
- 输出答案时大小写不敏感。题目大意： 一个 $n \times m$ 的字符网格被称为“great”，如果它满足以下三个条件： 1. 每个字符都是 'A'、'B' 或 'C' 之一。 2. 每个连续的 $2 \times 2$ 子网格都包含这三个不同的字母。 3. 任何共享公共边的两个单元格都包含不同的字母。 给定 $k$ 个约束，每个约束由两个共享一个角的单元格组成，需要构造一个满足所有约束的“great”网格。 输入输出数据格式： 输入： - 第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。 - 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n, m \le 2 \cdot 10^3$，$1 \le k \le 4 \cdot 10^3$）。 - 接下来的 $k$ 行，每行包含四个整数 $x_{i,1}$、$y_{i,1}$、$x_{i,2}$ 和 $y_{i,2}$（$1 \le x_{i,1} < x_{i,2} \le n$，$1 \le y_{i,1}, y_{i,2} \le m$），表示约束。保证 $(x_{i,2}, y_{i,2}) = (x_{i,1}+1, y_{i,1}+1)$ 或 $(x_{i,2}, y_{i,2}) = (x_{i,1}+1, y_{i,1}-1)$。 - 确保所有测试用例的 $n$ 之和不超过 $2 \cdot 10^3$，$m$ 之和不超过 $2 \cdot 10^3$，$k$ 之和不超过 $4 \cdot 10^3$。 输出： - 对于每个测试用例，如果存在满足所有约束的“great”网格，输出 "YES"，否则输出 "NO"。 - 输出答案时大小写不敏感。