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$$$ 卡片上写的数字。您应该以这样的方式在单元格 $$$(n, m)$$$ 中创建堆栈,以便对于所有 $$$1 \leq i \leq k$$$,$$$b_i = i$$$。
在一步操作中,您可以从单元格中取出最上面的牌并将其放置到相邻单元格(共享公共边的单元格)上。如果目标单元格已包含一张或多张牌,则将牌放在牌堆的顶部。您必须在满足以下限制的情况下执行每项操作:
- 除 $$$(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”将被识别为否定响应)。
示例
输入 #1
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
输出 #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)$$$。
上述过程的动画说明如下: