Таблицу размерами \(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» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных следующая прекрасная таблица удовлетворяет всем ограничениям:
Во втором наборе входных данных два ограничения означают, что в клетках \((1,1)\) и \((2,2)\) записаны одинаковые буквы, а также в клетках \((1,2)\) и \((2,1)\) записаны одинаковые буквы. Поэтому невозможно сделать так, чтобы единственная подтаблица \(2 \times 2\) содержала бы все три буквы хотя бы по разу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|