D. Карты знаний
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пак Чанек, известный ученый, изобрел карточную головоломку, используя свои знания. В головоломке вам дается поле с $$$n$$$ строками и $$$m$$$ столбцами. Пусть $$$(r, c)$$$ обозначает ячейку в $$$r$$$-й строке и $$$c$$$-м столбце.

Изначально в ячейке $$$(1, 1)$$$ стопкой лежат $$$k$$$ карт. На каждой карте написано целое число от $$$1$$$ до $$$k$$$. А именно, на $$$i$$$-й сверху карте в стопке в ячейке $$$(1, 1)$$$ написано число $$$a_i$$$. Известно, что не существует двух карт с одинаковыми числами. Другими словами, числа, написанные на картах, представляют собой перестановку целых чисел от $$$1$$$ до $$$k$$$. Все остальные ячейки пусты.

Вам нужно переместить все $$$k$$$ карт в ячейку $$$(n, m)$$$, чтобы составить другую стопку карт. Пусть $$$b_i$$$ — число, написанное на $$$i$$$-й сверху карте в стопке в ячейке $$$(n, m)$$$. Вы должны составить стопку в ячейке $$$(n, m)$$$ таким образом, чтобы $$$b_i = i$$$ для всех $$$1 \leq i \leq k$$$.

За один ход вы можете взять верхнюю карту из любой ячейки и положить ее на соседнюю ячейку (ячейку, имеющую общую сторону). Если ячейка, в которую вы собираетесь положить карту, уже содержит одну или несколько карт, вы кладете свою карту на вершину стопки. Вы должны выполнять каждую операцию, соблюдая следующие ограничения:

  • Каждая ячейка, отличная от $$$(1,1)$$$ и $$$(n,m)$$$, должна всегда содержать не более одной карты.
  • Вы не можете перемещать карту в ячейку $$$(1,1)$$$.
  • Вы не можете перемещать карту из ячейки $$$(n,m)$$$.

По заданным значениям $$$n$$$, $$$m$$$, $$$k$$$ и массиву $$$a$$$, определите, разрешима ли головоломка.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Следующие строки содержат описание наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$3 \leq n, m \leq 10^6$$$, $$$nm \leq 10^6$$$, $$$1 \leq k \leq 10^5$$$) — размеры поля и количество карт.

Вторая строка набора содержит $$$k$$$ целых чисел $$$a_1, a_2, \ldots, a_k$$$ — массив $$$a$$$, содержащий числа, написанные на картах. Значения $$$a$$$ представляют собой перестановку целых чисел от $$$1$$$ до $$$k$$$.

Гарантируется, что сумма $$$nm$$$ и сумма $$$k$$$ по всем наборам входных данных не превышают $$$10^6$$$ и $$$10^5$$$ соответственно.

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

Для каждого набора входных данных выведите «YA» (без кавычек), если головоломка имеет решение, и «TIDAK» (без кавычек) иначе, что означает «да» и «нет» соответственно в индонезийском языке.

Вы можете выводить «YA» и «TIDAK» в любом регистре (например, строки «tiDAk», «tidak» и «Tidak» будут восприняты как отрицательный ответ).

Пример
Входные данные
4
3 3 6
3 6 4 1 2 5
3 3 10
1 2 3 4 5 6 7 8 9 10
5 4 4
2 1 3 4
3 4 10
10 4 9 3 5 6 8 2 7 1
Выходные данные
YA
TIDAK
YA
YA
Примечание

В первом наборе входных данных головоломка может быть решена следующим образом:

  • Переместить карту с написанной на ней $$$3$$$ из ячейки $$$(1, 1)$$$ в ячейку $$$(1, 2)$$$, затем в $$$(1, 3)$$$.
  • Переместить карту с написанной на ней $$$6$$$ из ячейки $$$(1, 1)$$$ в ячейку $$$(2, 1)$$$, затем в $$$(3, 1)$$$, затем в $$$(3, 2)$$$, затем в $$$(3, 3)$$$.
  • Переместить карту с написанной на ней $$$4$$$ из ячейки $$$(1, 1)$$$ в ячейку $$$(1, 2)$$$.
  • Переместить карту с написанной на ней $$$1$$$ из ячейки $$$(1, 1)$$$ в ячейку $$$(2, 1)$$$, затем в $$$(2, 2)$$$, затем в $$$(2, 3)$$$.
  • Переместить карту с написанной на ней $$$2$$$ из ячейки $$$(1, 1)$$$ в ячейку $$$(2, 1)$$$, затем в $$$(2, 2)$$$.
  • Переместить карту с написанной на ней $$$5$$$ из ячейки $$$(1, 1)$$$ в ячейку $$$(2, 1)$$$, затем в $$$(3, 1)$$$, затем в $$$(3, 2)$$$, затем в $$$(3, 3)$$$.
  • Переместить карту с написанной на ней $$$2$$$ из ячейки $$$(2, 2)$$$ в ячейку $$$(2, 1)$$$.
  • Переместить карту с написанной на ней $$$4$$$ из ячейки $$$(1, 2)$$$ в ячейку $$$(2, 2)$$$, затем в $$$(3, 2)$$$, затем в $$$(3, 3)$$$.
  • Переместить карту с написанной на ней $$$3$$$ из ячейки $$$(1, 3)$$$ в ячейку $$$(1, 2)$$$, затем в $$$(2, 2)$$$, затем в $$$(3, 2)$$$, затем в $$$(3, 3)$$$.
  • Переместить карту с написанной на ней $$$2$$$ из ячейки $$$(2, 1)$$$ в ячейку $$$(3, 1)$$$, затем в $$$(3, 2)$$$, затем в $$$(3, 3)$$$.
  • Переместить карту с написанной на ней $$$1$$$ из ячейки $$$(2, 3)$$$ в ячейку $$$(3, 3)$$$.

Анимированная иллюстрация процесса, описанного выше, выглядит следующим образом: