Пак Чанек, известный ученый, изобрел карточную головоломку, используя свои знания. В головоломке вам дается поле с \(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\), определите, разрешима ли головоломка.
Выходные данные
Для каждого набора входных данных выведите «YA» (без кавычек), если головоломка имеет решение, и «TIDAK» (без кавычек) иначе, что означает «да» и «нет» соответственно в индонезийском языке.
Вы можете выводить «YA» и «TIDAK» в любом регистре (например, строки «tiDAk», «tidak» и «Tidak» будут восприняты как отрицательный ответ).
Примечание
В первом наборе входных данных головоломка может быть решена следующим образом:
- Переместить карту с написанной на ней \(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)\).
Анимированная иллюстрация процесса, описанного выше, выглядит следующим образом:
