Knowledge Cards
Contest: Codeforces Round 831 (Div. 1 + Div. 2)
Difficulty rating: 1500
Tags: constructive algorithms, data structures

Pak Chanek, a renowned scholar, invented a card puzzle using his knowledge. In the puzzle, you are given a board with $$$n$$$ rows and $$$m$$$ columns. Let $$$(r, c)$$$ represent the cell in the $$$r$$$-th row and the $$$c$$$-th column.

Initially, there are $$$k$$$ cards stacked in cell $$$(1, 1)$$$. Each card has an integer from $$$1$$$ to $$$k$$$ written on it. More specifically, the $$$i$$$-th card from the top of the stack in cell $$$(1, 1)$$$ has the number $$$a_i$$$ written on it. It is known that no two cards have the same number written on them. In other words, the numbers written on the cards are a permutation of integers from $$$1$$$ to $$$k$$$. All other cells are empty.

You need to move the $$$k$$$ cards to cell $$$(n, m)$$$ to create another stack of cards. Let $$$b_i$$$ be the number written on the $$$i$$$-th card from the top of the stack in cell $$$(n, m)$$$. You should create the stack in cell $$$(n, m)$$$ in such a way so that $$$b_i = i$$$ for all $$$1 \leq i \leq k$$$.

In one move, you can remove the top card from a cell and place it onto an adjacent cell (a cell that shares a common side). If the target cell already contains one or more cards, you place your card on the top of the stack. You must do each operation while satisfying the following restrictions:

- Each cell other than $$$(1,1)$$$ and $$$(n,m)$$$ must not have more than one card on it.
- You cannot move a card onto cell $$$(1,1)$$$.
- You cannot move a card from cell $$$(n,m)$$$.

Given the values of $$$n$$$, $$$m$$$, $$$k$$$ and the array $$$a$$$, determine if the puzzle is solvable.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$3 \leq n, m \leq 10^6$$$, $$$nm \leq 10^6$$$, $$$1 \leq k \leq 10^5$$$) — the size of the board and the number of cards.

The second line of the test case contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ — the array $$$a$$$, representing the numbers written on the cards. The values of $$$a$$$ are a permutation of integers from $$$1$$$ to $$$k$$$.

It is guaranteed that the sum of $$$nm$$$ and $$$k$$$ over all test cases do not exceed $$$10^6$$$ and $$$10^5$$$ respectively.

Output format:
For each test case, output "YA" (without quotes) if it is possible and "TIDAK" (without quotes) otherwise, which mean yes and no in Indonesian respectively.

You can output "YA" and "TIDAK" in any case (for example, strings "tiDAk", "tidak", and "Tidak" will be recognised as a negative response).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the following is one way the puzzle can be done:

- Move the card with $$$3$$$ written on it from cell $$$(1, 1)$$$ to cell $$$(1, 2)$$$, then cell $$$(1, 3)$$$.
- Move the card with $$$6$$$ written on it from cell $$$(1, 1)$$$ to cell $$$(2, 1)$$$, then cell $$$(3, 1)$$$, then cell $$$(3, 2)$$$, then cell $$$(3, 3)$$$.
- Move the card with $$$4$$$ written on it from cell $$$(1, 1)$$$ to cell $$$(1, 2)$$$.
- Move the card with $$$1$$$ written on it from cell $$$(1, 1)$$$ to cell $$$(2, 1)$$$, then cell $$$(2, 2)$$$, then cell $$$(2, 3)$$$.
- Move the card with $$$2$$$ written on it from cell $$$(1, 1)$$$ to cell $$$(2, 1)$$$, then cell $$$(2, 2)$$$.
- Move the card with $$$5$$$ written on it from cell $$$(1, 1)$$$ to cell $$$(2, 1)$$$, then cell $$$(3, 1)$$$, then cell $$$(3, 2)$$$, then cell $$$(3, 3)$$$.
- Move the card with $$$2$$$ written on it from cell $$$(2, 2)$$$ to cell $$$(2, 1)$$$.
- Move the card with $$$4$$$ written on it from cell $$$(1, 2)$$$ to cell $$$(2, 2)$$$, then cell $$$(3, 2)$$$, then cell $$$(3, 3)$$$.
- Move the card with $$$3$$$ written on it from cell $$$(1, 3)$$$ to cell $$$(1, 2)$$$, then cell $$$(2, 2)$$$, then cell $$$(3, 2)$$$, then cell $$$(3, 3)$$$.
- Move the card with $$$2$$$ written on it from cell $$$(2, 1)$$$ to cell $$$(3, 1)$$$, then cell $$$(3, 2)$$$, then cell $$$(3, 3)$$$.
- Move the card with $$$1$$$ written on it from cell $$$(2, 3)$$$ to cell $$$(3, 3)$$$.

An animated illustration regarding the process mentioned above is as follows:

Example input:
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

Example output:
YA
TIDAK
YA
YA

Editorial:
Let card $$$c$$$ be the card with number $$$c$$$ written on it. Notice that we must put the cards into the stack in $$$(n,m)$$$ in order from card $$$k$$$, card $$$k-1$$$, card $$$k-2$$$, and so on until card $$$1$$$.
The key observation for this problem is that, under given constraints, if we ignore cells $$$(1,1)$$$ and $$$(n,m)$$$ we can always move any card to either $$$(n-1,m)$$$ or $$$(n,m-1)$$$ if and only if there is at least one empty cell. We can obtain this by considering the fact that an empty cell can "move" to any cell and can be used to rotate any $$$2 \times 2$$$ square of cells. Because $$$3 \leq n, m$$$, if we ignore cells $$$(1,1)$$$ and $$$(n,m)$$$, each cell is a part of a $$$2 \times 2$$$ square. Moving a desired card to a one of $$$(n-1,m)$$$ or $$$(n,m-1)$$$ can be done by firstly moving the empty cell to be adjacent to the desired card, and then only doing $$$2 \times 2$$$ rotations that simultaneously move the empty cell and the desired card.
Therefore, we can iterate the card in the stack $$$(1, 1)$$$ from top to bottom. While iterating, one should maintain all of the cards in the board that are not in cell $$$(1, 1)$$$ or $$$(n, m)$$$. We define those group of cards as active cards. Each time we put a move a card out of $$$(1, 1)$$$, we add the card to the active cards. Before finishing the iteration we will try to move one or more cards from the active cards to $$$(n, m)$$$ as long as there is a card we can move. We can maintain the active cards with a priority queue or a set.
The active cards can be moved around freely if and only if there is at least one empty cell in the grid if we ignore $$$(1,1)$$$ and $$$(n,m)$$$. Therefore, to check whether or not we can solve the puzzle, we just need to check whether or not there exists a moment where the number of active cards exceed $$$nm-3$$$.
There also exists a solution with a time complexity of $$$O(k)$$$ just by iterating the positions of each card number, but it will not be explained here.
Time complexity for each test case: $$$O(k\log k)$$$ or $$$O(k)$$$