E. Прекрасные таблицы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Таблицу размерами $$$n \times m$$$, состоящую из символов, назовём прекрасной, если она удовлетворяет следующим трём условиям:

  • Каждый символ — это 'A', 'B' или 'C'.
  • В любой непрерывной подтаблице размерами $$$2 \times 2$$$ каждая из трёх букв встречается хотя бы один раз.
  • В любых двух клетках, имеющих общую сторону, записаны разные буквы.

Через $$$(x,y)$$$ обозначим клетку на пересечении $$$x$$$-й сверху строки и $$$y$$$-го слева столбца.

Вы хотите построить прекрасную таблицу, которая бы также удовлетворяла $$$k$$$ ограничениям. Каждое ограничение задаёт условие на две клетки — $$$(x_{i,1},y_{i,1})$$$ и $$$(x_{i,2},y_{i,2})$$$, которые имеют ровно один общий угол. Вы хотите, чтобы в вашей таблице в клетках $$$(x_{i,1},y_{i,1})$$$ и $$$(x_{i,2},y_{i,2})$$$ были записаны одинаковые буквы.

Определите, существует ли прекрасная таблица, удовлетворяющая всем ограничениям.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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)$$$.

Пары клеток попарно различны, т. е. для всех $$$1 \le i < j \le k$$$ неверно, что $$$x_{i,1} = x_{j,1}$$$, $$$y_{i,1} = y_{j,1}$$$, $$$x_{i,2} = x_{j,2}$$$ и $$$y_{i,2} = y_{j,2}$$$ одновременно.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^3$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^3$$$.

Гарантируется, что сумма значений $$$k$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^3$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если существует прекрасная таблица, удовлетворяющая всем ограничениям. Иначе выведите «NO».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
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
Выходные данные
YES
NO
YES
NO
Примечание

В первом наборе входных данных следующая прекрасная таблица удовлетворяет всем ограничениям:

BABC
CBCA
ACAB

Во втором наборе входных данных два ограничения означают, что в клетках $$$(1,1)$$$ и $$$(2,2)$$$ записаны одинаковые буквы, а также в клетках $$$(1,2)$$$ и $$$(2,1)$$$ записаны одинаковые буквы. Поэтому невозможно сделать так, чтобы единственная подтаблица $$$2 \times 2$$$ содержала бы все три буквы хотя бы по разу.