[思维]Knowledge Cards Codeforces1740D

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

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

YA
TIDAK
YA
YA

题意： 在一个n*m的棋盘上有k个数字，开始时它们叠起来位于(1, 1)，现在要让它们移动至(n, m)且叠起来的顺序变成降序，问是否可能做到。

分析： 首先最后顺序是降序，所以要先把最下面的数字也就是最大的数字x移动到(n, m)，这就需要在(1, 1)位置上的在x上面的数字先移动到棋盘上的其他位置，如果此时棋盘上没有空位容纳其它数字了那就说明误解，而x上面有多少个有效数字可以用树状数组维护出来，就是它上面数字个数减去已经移到终点的数字个数，设这个值为num，那么num应该小于等于棋盘上的空位数，棋盘上能放其他数字的空位数应该是n*m-4，减去的四个点分别是起点、终点、从起点出来的落脚点、用于不断移动的空位。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#define lowbit(x) -x&x
using namespace std;
 
int a[100005], pos[100005], c[100005];
int n, m, k;
 
int sum(int x){
	int ans = 0;
	for(int i = x; i >= 1; i-=lowbit(i))
		ans += c[i];
	return ans;
}
 
void add(int x, int v){
	for(int i = x; i <= k; i+=lowbit(i))
		c[i] += v;
}
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		scanf("%d%d%d", &n, &m, &k);
		for(int i = 1; i <= k; i++){
			scanf("%d", &a[i]);
			pos[a[i]] = i;
			c[i] = 0;
		}
		bool flag = true;
		for(int i = k; i >= 1; i--){
			int num = pos[i]-1-sum(pos[i]);
			if(m*n-4 < num)
				flag = false;
			add(pos[i], 1);
		}
		if(flag) puts("YA");
		else puts("TIDAK");
	}
	return 0;
}