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

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

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


-----Examples-----

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


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

Source: codeforces | Difficulty: MEDIUM
Tags: Data structures

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	(n, m, k) = readInts()
	arr = readList()
	isPresent = [False] * (k + 1)
	curr = k
	cnt = 0
	for i in range(k):
		if arr[i] == curr:
			if cnt < n * m - 3:
				curr -= 1
				continue
			return 'TIDAK'
		else:
			while isPresent[curr] and curr > 0 and (cnt <= n * m - 3):
				isPresent[curr] = False
				cnt -= 1
				curr -= 1
			isPresent[arr[i]] = True
			cnt += 1
			if cnt > n * m - 2:
				return 'TIDAK'
	return 'YA'
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m, k) = map(int, input().strip().split())
	l = list(map(int, input().strip().split()))
	lk = [i for i in range(k, 0, -1)]
	p = n * m - 3
	ans = ''
	if p >= k:
		ans = 'YA'
	else:
		co = 0
		for i in range(k):
			if l[i] > lk[i]:
				co = max(co, l[i] - lk[i])
		if p > co:
			ans = 'YA'
		else:
			ans = 'TIDAK'
	print(ans)


import sys
import heapq
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	chk = n * m - 4
	s = 0
	d = {}
	c = 0
	for i in range(k):
		if k in d:
			c -= 1
			k -= 1
		if l[i] == k:
			k -= 1
		else:
			d[l[i]] = 1
			c += 1
		if c > chk:
			print('TIDAK')
			break
	else:
		print('YA')


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def values():
	return list(map(int, sys.stdin.readline().split()))

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(sys.stdin.readline())

def instr():
	return sys.stdin.readline().strip()

def words():
	return [i for i in sys.stdin.readline().strip().split()]

def chars():
	return [i for i in sys.stdin.readline().strip()]

def solve():
	(n, m, k) = values()
	l = values()
	mx = m * n - 4
	h = []
	req = k
	for i in l:
		heapq.heappush(h, -i)
		while h and req == -h[0]:
			heapq.heappop(h)
			req -= 1
		if len(h) > mx:
			return 'TIDAK'
	return 'YA'
for i in range(inp()):
	print(solve())


def my_function(ms, sz, k):
	if sz - k >= 3:
		print('YA')
		return
	my_dic = {}
	for index in range(k):
		my_dic[ms[index]] = index + 1
	cnt = sz
	for index in range(k, 0, -1):
		if cnt - my_dic[index] < 3:
			print('TIDAK')
			return
		else:
			cnt += 1
	print('YA')

def alg(mass):
	for arr in mass:
		ms = arr['arr']
		sz = arr['sz']
		k = arr['k']
		my_function(ms, sz, k)

def parsing():
	cnt = int(input())
	mass = []
	while cnt > 0:
		st = input().split(' ')
		(n, m, k) = (int(st[0]), int(st[1]), int(st[2]))
		arr = list(map(int, input().split(' ')))
		mass.append({'sz': n * m, 'k': k, 'arr': arr})
		cnt -= 1
	return mass
res = parsing()
alg(res)


import sys

def read():
	return [int(x) for x in sys.stdin.readline().split(' ')]
[t] = read()
for _ in range(t):
	[n, m, k] = read()
	A = read()
	for i in range(len(A)):
		A[i] -= 1
	l = n * m - 3
	done = k * [0]
	acc = 0
	next = k - 1
	ok = True
	for a in A:
		acc += 1
		done[a] = 1
		if a != next:
			continue
		if acc > l:
			ok = False
			break
		while next and done[next]:
			acc -= 1
			next -= 1
	print('YA' if ok else 'TIDAK')


t = int(input())
for _ in range(t):
	(n, m, k) = [int(x) for x in input().split()]
	lst = [int(x) for x in input().split()]
	empty = n * m - 3
	if k <= empty:
		print('YA')
	else:
		i = 0
		count = 0
		mp = {}
		ans = True
		while empty < k and count <= empty:
			if k in mp:
				del mp[k]
				count = count - 1
				k = k - 1
			else:
				mp[lst[i]] = 1
				i = i + 1
				count = count + 1
				if count == empty + 1:
					ans = False
					break
		if ans == True:
			print('YA')
		else:
			print('TIDAK')


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n * m - 2 > k:
		print('YA')
		continue
	pos = n * m - 3
	isPosib = True
	while pos < len(a):
		if a[pos] >= k:
			isPosib = False
			break
		k -= 1
		pos += 1
	if not isPosib:
		print('TIDAK')
		continue
	print('YA')


def solve() -> None:
	(n, m, k) = map(int, input().split())
	cards = list(map(int, input().split()))
	have = [False] * (k + 1)
	need_card = k
	occupied = 0
	for card in cards:
		if card == need_card:
			if occupied == n * m - 3:
				print('TIDAK')
				return
			need_card -= 1
			while need_card >= 1 and have[need_card]:
				occupied -= 1
				need_card -= 1
		else:
			occupied += 1
			have[card] = True
			if occupied > n * m - 3:
				print('TIDAK')
				return
	print('YA')
tt = int(input())
for _ in range(tt):
	solve()


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	freeCells = n * m - (n + m - 1)
	buffers = n * m - freeCells - 4
	for i in range(k):
		if i - k + a[i] > freeCells + buffers:
			print('TIDAK')
			break
	else:
		print('YA')


import heapq

def sol(lst, n, m, k):
	heap = []
	counter = 0
	k_star = k
	for num in lst:
		counter += 1
		heapq.heappush(heap, -num)
		while heap and -heap[0] == k_star:
			counter -= 1
			heapq.heappop(heap)
			k_star -= 1
		if counter == n * m - 3:
			return 'TIDAK'
	return 'YA'
T = int(input())
for test_case in range(1, T + 1):
	(n, m, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	s = sol(lst, n, m, k)
	print(s)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cap = m * n - 4
	d = {}
	need = k
	i = 0
	flag = False
	while need > 0:
		if need in d:
			need -= 1
			cap += 1
		elif a[i] == need:
			need -= 1
			i += 1
		else:
			if cap == 0:
				flag = True
				break
			cap -= 1
			d[a[i]] = 1
			i += 1
	if flag:
		print('TIDAK')
	else:
		print('YA')


import os
import math
import collections
import bisect
import functools
import itertools
import heapq
from collections import deque

def solve(q, m, n, k):
	visited = set()
	for y in range(k, 0, -1):
		if y in visited:
			visited.remove(y)
			continue
		while q and q[0] != y:
			visited.add(q.popleft())
		q.popleft()
		if len(visited) > m * n - 4:
			return 'TIDAK'
	return 'YA'
t = int(input())
for _ in range(t):
	(m, n, k) = map(int, input().split())
	if m > n:
		(m, n) = (n, m)
	a = deque(map(int, input().split()))
	res = solve(a, m, n, k)
	print(res)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	idx = [i for i in range(k, 0, -1)]
	ans = 'YA'
	if n * m - 3 < k:
		mx = 0
		for i in range(k):
			if arr[i] > idx[i]:
				mx = max(mx, arr[i] - idx[i])
		if n * m - 4 < mx:
			ans = 'TIDAK'
	print(ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	covered = {x: i for (i, x) in enumerate(a)}
	avail = n * m - 4
	for i in range(k, 0, -1):
		o = k - i
		if covered[i] - o > avail:
			print('TIDAK')
			break
	else:
		print('YA')


t = int(input())
while t > 0:
	(n, m, k) = map(int, input().split())
	cards = list(map(int, input().split()))
	onBoard = {}
	freeSpots = n * m - 2
	cardNo = 0
	reqd = k
	freeSpotmin = 2
	if m == 2 and n == 2:
		freeSpotmin = 1
	while freeSpots >= freeSpotmin and cardNo < k:
		card = cards[cardNo]
		if card != reqd:
			onBoard[card] = 1
			freeSpots -= 1
		else:
			reqd -= 1
			while reqd in onBoard:
				del onBoard[reqd]
				reqd -= 1
				freeSpots += 1
		cardNo += 1
	if freeSpots < freeSpotmin:
		print('TIDAK')
	else:
		print('YA')
	t -= 1


def main():
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ind = [0] * (k + 1)
	for i in range(k):
		ind[arr[i]] = i
	aux = n * m - 4
	card = k
	curr = 0
	while card > 0:
		index = ind[card]
		if curr > index:
			aux += 1
			card -= 1
			continue
		elif curr == index:
			card -= 1
			curr += 1
			continue
		else:
			req = index - curr
			if req <= aux:
				aux -= req
				curr = index + 1
				card -= 1
			else:
				return 'TIDAK'
	return 'YA'
for _ in range(int(input())):
	print(main())


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n, m, k) = inp_arr()
	a = inp_arr()
	hp = []
	heapq.heapify(hp)
	cap = n * m - 4
	need = k
	for x in a:
		while len(hp) > 0 and abs(hp[0]) == need:
			heapq.heappop(hp)
			need -= 1
		if x == need:
			need -= 1
		elif len(hp) == cap:
			print('TIDAK')
			return
		else:
			heapq.heappush(hp, -x)
	print('YA')
(tt,) = inp_arr()
for t in range(tt):
	solve()


I = lambda : int(input())
Is = lambda : map(int, input().split())
Li = lambda : list(map(int, input().split()))

def solve():
	(n, m, k) = Is()
	a = Li()
	s = n * m - 2
	seen = set()
	cur = k
	po = 0
	for i in a:
		seen.add(i)
		po += 1
		if po == s:
			print('TIDAK')
			return
		if i == k:
			po -= 1
			seen.remove(i)
			cur -= 1
		while cur in seen:
			po -= 1
			seen.remove(cur)
			cur -= 1
	print('YA')
	return 1
t = I()
while t:
	solve()
	t -= 1


import heapq
import sys

def solution(row, col, target, order):
	max_heap = []
	limit = row * col - 2
	for element in order:
		heapq.heappush(max_heap, (-element, element))
		if len(max_heap) == limit:
			break
		while len(max_heap) != 0 and max_heap[0][1] == target:
			target -= 1
			heapq.heappop(max_heap)
	if len(max_heap) != 0:
		return 'TIDAK'
	else:
		return 'YA'
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m, k) = tuple(map(int, input().split()))
	order = list(map(int, input().split()))
	print(solution(n, m, k, order))


t = int(input())
while t > 0:
	ip = [int(x) for x in input().split()]
	n = ip[0]
	m = ip[1]
	k = ip[2]
	a = [int(x) for x in input().split()]
	freq = []
	val = k
	count = n * m - 4
	for i in range(k + 1):
		freq.append(0)
	flag = True
	for i in a:
		if i == k:
			k -= 1
			while freq[k] > 0:
				freq[k] -= 1
				count += 1
				k -= 1
		elif count > 0:
			freq[i] += 1
			count -= 1
		else:
			flag = False
			break
	if flag:
		print('YA')
	else:
		print('TIDAK')
	t -= 1


t = int(input())
for _ in range(t):
	(m, n, p) = [int(x) for x in input().split()]
	permut = [int(x) for x in input().split()]
	s = set()
	i = 0
	flag = 0
	for need in range(p, 0, -1):
		while True:
			if flag == 1:
				break
			if need in s:
				s.remove(need)
				break
			elif len(s) == m * n - 3:
				print('TIDAK')
				flag = 1
			else:
				s.add(permut[i])
				i += 1
		if flag == 1:
			break
	if flag != 1:
		print('YA')


def f(n, m, arr):
	k = len(arr)
	on_board = set()
	max_size = n * m - 2
	for i in range(k, 0, -1):
		if i in on_board:
			on_board.remove(i)
			continue
		while arr[-1] != i and len(on_board) < max_size:
			top_value = arr.pop()
			on_board.add(top_value)
		if len(on_board) >= max_size - 1:
			return False
		arr.pop()
	return True
t = int(input())
for i in range(t):
	(n, m, k) = [int(el) for el in input().split(' ')]
	arr = [int(el) for el in input().split(' ')]
	r_arr = list(reversed(arr))
	if f(n, m, r_arr):
		print('YA')
	else:
		print('TIDAK')


t = int(input())
for x in range(t):
	S = list(map(int, input().split()))
	(n, m, k) = (S[0], S[1], S[2])
	stack = list(map(int, input().split()))
	count = 0
	d = dict()
	for i in range(k):
		d[stack[i]] = i
	for i in range(k, 0, -1):
		if d[i] > m * n - 4 + k - i:
			count = 1
			print('TIDAK')
			break
	if count == 0:
		print('YA')


def solve(n, m, k, a):
	d = {}
	val = n * m - 4
	nxt = k
	p1 = 0
	while p1 < k:
		if a[p1] == nxt:
			nxt -= 1
			while True:
				try:
					d[nxt] -= 1
					nxt -= 1
					val += 1
				except:
					break
		else:
			try:
				d[nxt] -= 1
				val += 1
				nxt -= 1
			except:
				d[a[p1]] = 1
				val -= 1
		if val < 0:
			return 'TIDAK'
		p1 += 1
	return 'YA'
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(m, n, k, a))


import heapq

def sol(lst, n, m, k):
	counter = 0
	h = []
	to_insert = k
	maxi = n * m - 3
	for num in lst:
		counter += 1
		heapq.heappush(h, -num)
		while h and -h[0] == to_insert:
			counter -= 1
			heapq.heappop(h)
			to_insert -= 1
		if counter == maxi:
			return 'TIDAK'
	return 'YA'
T = int(input())
for test_case in range(1, T + 1):
	(n, m, k) = [int(s) for s in input().split(' ')]
	lst = [int(s) for s in input().split(' ')]
	s = sol(lst, n, m, k)
	print(s)


t = int(input())
for _ in range(t):
	(n, m, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	wait_set = set([])
	wait_len = 0
	max_len = n * m - 4
	answer = 'YA'
	M = k
	i = 0
	while M > 0:
		if M not in wait_set:
			x = a[i]
			if x != M:
				wait_set.add(x)
				wait_len += 1
				i += 1
			else:
				M = M - 1
				i += 1
		else:
			wait_set.remove(M)
			wait_len -= 1
			M = M - 1
		if wait_len > max_len:
			answer = 'TIDAK'
			break
	print(answer)


t = int(input(''))
for j in range(t):
	l = list(map(int, input('').split()))
	n = l[0]
	m = l[1]
	k = l[2]
	s = [0] * (k + 1)
	s[0] = 0
	c = 0
	l = list(map(int, input('').split()))
	a = n * m - 4
	if a >= k - 1:
		print('YA')
		continue
	for i in l:
		if i != k:
			s[i] = 1
			c += 1
		else:
			k = k - 1
			while s[k] == 1:
				c -= 1
				s[k] = 0
				k -= 1
		if c >= a + 1:
			print('TIDAK')
			break
	else:
		print('YA')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = [x - 1 for x in list(map(int, input().split()))]
	(kosong, sekarang) = (n * m - 2, k - 1)
	(ok, bisa) = ([0] * k, True)
	for i in range(k):
		ok[a[i]] = 1
		kosong -= 1
		if kosong <= 0:
			print('TIDAK')
			bisa = False
			break
		while sekarang >= 0 and ok[sekarang]:
			sekarang -= 1
			kosong += 1
	if bisa:
		print('YA')


t = int(input())
for i in range(t):
	(n, m, k) = [int(v) for v in input().split()]
	w = [int(v) for v in input().split()][::-1]
	rho = n * m - 4
	zeta = k
	eta = 0
	res = set()
	while zeta > 0:
		if w:
			if eta <= rho:
				eta += 1
				res.add(w.pop())
			else:
				print('TIDAK')
				break
		else:
			zeta = 0
			continue
		while zeta in res:
			res.remove(zeta)
			zeta -= 1
			eta -= 1
	else:
		print('YA')


import heapq
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	cur_element = max(arr)
	max_heap_size = n * m - 4
	max_heap = []
	invalid = False
	for i in range(k):
		if arr[i] == cur_element:
			cur_element -= 1
			while max_heap and -max_heap[0] == cur_element:
				heapq.heappop(max_heap)
				cur_element -= 1
		else:
			heapq.heappush(max_heap, -arr[i])
			if len(max_heap) > max_heap_size:
				invalid = True
				break
	if invalid:
		print('TIDAK')
	else:
		print('YA')


from collections import defaultdict
for _ in range(int(input())):
	a0 = [int(x) for x in input().split()]
	(n, m, k) = (a0[0], a0[1], a0[2])
	(cur, cnt, ans, target) = (k, 0, 0, n * m - 3)
	d = defaultdict(int)
	a = [int(x) for x in input().split()]
	for i in range(k):
		flag = 0
		while d[cur] == 0 and cnt < k:
			idx = cnt
			d[a[idx]] = d[a[idx]] + 1
			cnt += 1
			ans += 1
		if target < ans:
			flag = 1
			print('TIDAK')
			break
		if flag == 1:
			continue
		ans -= 1
		cur -= 1
	if flag == 0:
		print('YA')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	f = [0] * (k + 5)

	def get(i):
		ans = 0
		while i > 0:
			ans += f[i]
			i -= -i & i
		return ans

	def up(i):
		while i <= k:
			f[i] += 1
			i += -i & i
	ok = True
	for e in a:
		if get(e) > m * n - 4:
			print('TIDAK')
			ok = False
			break
		else:
			up(e)
	if ok:
		print('YA')


import sys
input = sys.stdin.readline
import queue
for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	res = []
	pq = queue.PriorityQueue()
	for i in lst[:n * m - 4]:
		pq.put(-i)
	for i in lst[n * m - 4:]:
		pq.put(-i)
		res.append(-pq.get())
	while not pq.empty():
		res.append(-pq.get())
	res = res[::-1]
	for i in range(len(res) - 1):
		if res[i + 1] < res[i]:
			print('TIDAK')
			break
	else:
		print('YA')


class FenwickTree:

	def __init__(self, n):
		self.bit = [0] * n
		self.size = n

	def update(self, idx, x):
		while idx < self.size:
			self.bit[idx] += x
			idx |= idx + 1

	def __call__(self, start, end):
		return self.__getitem__(end) - self.__getitem__(start)

	def __getitem__(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x

	def find_kth(self, k):
		idx = -1
		for d in reversed(range(self.size.bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < self.size and self.bit[right_idx] <= k:
				idx = right_idx
				k -= self.bit[idx]
		return (idx + 1, k)
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = [k - x for x in list(map(int, input().split()))]
	pos = [0] * k
	for i in range(k):
		pos[a[i]] = i
	F = FenwickTree(k)
	for i in range(k):
		F.update(i, 1)
	ok = True
	for i in range(k):
		now = pos[i]
		num = F(0, now)
		if num > n * m - 4:
			print('TIDAK')
			ok = False
			break
		F.update(now, -1)
	if ok:
		print('YA')