CF1740D.Knowledge Cards

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.

著名学者 Pak Chanek 凭借其渊博的知识发明了一种卡片谜题。在该谜题中，你将获得一个具有 $n$ 行 $m$ 列的棋盘。记 $(r, c)$ 表示第 $r$ 行、第 $c$ 列的格子。

初始时，有 $k$ 张卡片堆叠在格子 $(1, 1)$ 中。每张卡片上写有一个 $1$ 到 $k$ 之间的整数。具体而言，在格子 $(1, 1)$ 的卡片堆中，从上往下数第 $i$ 张卡片上写的数字为 $a_i$。已知任意两张卡片上的数字互不相同，即这些数字恰好构成 $1$ 到 $k$ 的一个排列。其余所有格子均为空。

你需要将这 $k$ 张卡片全部移动到格子 $(n, m)$，从而在该格子中形成一个新的卡片堆。设 $b_i$ 表示最终在格子 $(n, m)$ 的卡片堆中、从上往下数第 $i$ 张卡片上所写的数字。你必须使得对所有 $1 \leq i \leq k$，均有 $b_i = i$。

每次操作中，你可以从某个格子顶部取走一张卡片，并将其放置到一个相邻格子（即与当前格子有一条公共边的格子）上。若目标格子中已有一张或多张卡片，则你须将取出的卡片置于该格子卡片堆的最顶端。你必须在满足以下限制的前提下执行每一次操作：

• 除 $(1,1)$ 和 $(n,m)$ 外，其余每个格子上至多只能有一张卡片；
• 你不能将任何卡片移动到格子 $(1,1)$；
• 你不能从格子 $(n,m)$ 移出任何卡片。

给定 $n$、$m$、$k$ 的值以及数组 $a$，判断该谜题是否可解。

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.

每个测试包含多个测试用例。第一行包含一个整数 $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$ 的总和不超过 $10^6$，且 $k$ 的总和不超过 $10^5$。

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).

对于每个测试用例，如果可能则输出 "YA"（不带引号），否则输出 "TIDAK"（不带引号），它们在印尼语中分别表示“是”和“否”。

你可以以任意大小写形式输出 "YA" 和 "TIDAK"（例如，字符串 "tiDAk"、"tidak" 和 "Tidak" 均会被识别为否定回答）。

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:

在第一个测试用例中，以下是一种完成该谜题的方法：

• 将写有数字 $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)$。

关于上述过程的动画演示如下：