eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

2D-Нім

2D-Нім

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У настольну гру 2D–нім грають на дошці у вигляді сітки, у вузлах якої можуть знаходитись фішки. Хід гравця полягає у видаленні довільної додатньої кількості підряд ідучих фішок у довільному рядку або у довільному стовбці. Наприклад, розглянемо ліву дошку на наступній картинці:

Гравець може видалити фішки (A), (B), (A, B), (A, B, C), або (B, F), і так далі. Але він не може видалити (A, C), (D, E), (H, I) або (B, G).

З метою написання програмного забезпечення для гри у 2D–нім, програміст хоче мати можливість визначати, чи була деяка позиція проаналізована раніше. Із правил гри слідує, що дві вище представлені позиції еквівалентні. Тобто, якщо існує вигршна стратегія для позиції ліворуч, то ця ж стратегія повинна застосовуватись для досягнення виграшу і для позиції праворуч. Послідовні групи фішок можуть появлятись у довільному місці і в довільній орієнтації. Тобто на обох дошах можуть появлятись одні і ті ж кластери фішок (кластером називається множина рядом стоячих фішок, які досягаються міжд собою послідовністю одноклітинних ходів по горизонталі або вертикалі). Наприклад, кластер з фішок (A, B, C, F, G) зустрічається на обох дошках, хоча він віддзеркалений (зправа наліво), повернутий і зсунутий.

Ваша задача – визначити, чи є дві задані позиції еквівалентними у описаному вище розумінні.

Вхідні дані

Перший рядок містить єдине число – кількість тестів t (1t10). Перший рядок кожного тесту містить три цілих числа W, H і n (1W, H100). Тут W – ширина, а H – висота ігрової дошки, які вимірюються кількістю вузлів сітки. n – кількість фішок на дошці. Другий рядок містить n пар цілих чисел (x_i, y_i), які описують координати фішок на першій дошці (0x_iW, 0y_iH). Третій рядок описує координати фішок на другій дошці у тому ж форматі.

Вихідні дані

Для кожного тесту вивести YES або NO у залежності від того, чи є дві задані позиції еквівалентними.

Приклад

Вхідні дані #1
2
8 5 11
0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 5 2 4 4
0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4
8 5 11
0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 6 1 4 4
0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4
Вихідні дані #1
YES
NO
Джерело Tehran 2002, First Iran Nationwide Internet Programming Contest