# Knowledge Cards solution codeforces

Knowledge Cards solution codeforces

Knowledge Cards
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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)(1,1). Each card has an integer fromĀ 11Ā toĀ škĀ written on it. More specifically, theĀ ši-th cardĀ from the topĀ of the stack in cellĀ (1,1)(1,1)Ā has the numberĀ ššaiĀ 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Ā 11Ā 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Ā ššbiĀ 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Ā šš=šbi=iĀ for allĀ 1ā¤šā¤š1ā¤iā¤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)(1,1)Ā andĀ (š,š)(n,m)Ā must not have more than one card on it.
• You cannot move a card onto cellĀ (1,1)(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

Each test contains multiple test cases. The first line contains an integerĀ š”tĀ (1ā¤š”ā¤2ā1041ā¤tā¤2ā104) ā 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ā¤š,šā¤1063ā¤n,mā¤106,Ā ššā¤106nmā¤106,Ā 1ā¤šā¤1051ā¤kā¤105) ā the size of the board and the number of cards.

The second line of the test case containsĀ škĀ integersĀ š1,š2,ā¦,šša1,a2,ā¦,akĀ ā the arrayĀ ša, representing the numbers written on the cards. The values ofĀ šaĀ are a permutation of integers fromĀ 11Ā toĀ šk.

It is guaranteed that the sum ofĀ ššnmĀ andĀ škĀ over all test cases do not exceedĀ 106106Ā andĀ 105105Ā respectively.

Output

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

Example
input

Copy
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
output

Copy
YA
TIDAK
YA
YA

Note

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

• Move the card withĀ 33Ā written on it from cellĀ (1,1)(1,1)Ā to cellĀ (1,2)(1,2), then cellĀ (1,3)(1,3).
• Move the card withĀ 66Ā written on it from cellĀ (1,1)(1,1)Ā to cellĀ (2,1)(2,1), then cellĀ (3,1)(3,1), then cellĀ (3,2)(3,2), then cellĀ (3,3)(3,3).
• Move the card withĀ 44Ā written on it from cellĀ (1,1)(1,1)Ā to cellĀ (1,2)(1,2).
• Move the card withĀ 11Ā written on it from cellĀ (1,1)(1,1)Ā to cellĀ (2,1)(2,1), then cellĀ (2,2)(2,2), then cellĀ (2,3)(2,3).
• Move the card withĀ 22Ā written on it from cellĀ (1,1)(1,1)Ā to cellĀ (2,1)(2,1), then cellĀ (2,2)(2,2).
• Move the card withĀ 55Ā written on it from cellĀ (1,1)(1,1)Ā to cellĀ (2,1)(2,1), then cellĀ (3,1)(3,1), then cellĀ (3,2)(3,2), then cellĀ (3,3)(3,3).
• Move the card withĀ 22Ā written on it from cellĀ (2,2)(2,2)Ā to cellĀ (2,1)(2,1).
• Move the card withĀ 44Ā written on it from cellĀ (1,2)(1,2)Ā to cellĀ (2,2)(2,2), then cellĀ (3,2)(3,2), then cellĀ (3,3)(3,3).
• Move the card withĀ 33Ā written on it from cellĀ (1,3)(1,3)Ā to cellĀ (1,2)(1,2), then cellĀ (2,2)(2,2), then cellĀ (3,2)(3,2), then cellĀ (3,3)(3,3).
• Move the card withĀ 22Ā written on it from cellĀ (2,1)(2,1)Ā to cellĀ (3,1)(3,1), then cellĀ (3,2)(3,2), then cellĀ (3,3)(3,3).
• Move the card withĀ 11Ā written on it from cellĀ (2,3)(2,3)Ā to cellĀ (3,3)(3,3).

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