Programming Contest

Byteman is preparing for the final round of an individual programming contest. While preparing, he carefully read both the terms and conditions and the organizational rules, and learned that the final round will contain exactly $n$ tasks, each belonging to one of $k$ topics. Several tasks may come from the same topic. Byteman knows every finalist well, so for each participant he knows her skill in every topic. A skill is a positive integer, and the larger it is, the higher the skill.

Every task has a difficulty given as a positive integer. Byteman assumes that a participant solves a task only if her skill in that task's topic is at least the task's difficulty. For each task she solves, a participant earns points equal to (her skill in that topic) minus (the task's difficulty). In the final ranking, a participant who solves more tasks is always ranked higher; among participants who solve the same number of tasks, the one with more points is ranked higher.

Instead of training hard, Byteman started wondering whether there is a set of tasks for which he would win. He finds this hard to decide, so he asked you for help. If Byteman ties for first place, he does not win. You may choose each task's topic and difficulty freely; decide whether a set of tasks exists that makes Byteman the sole winner.

The first line of standard input contains a single integer $t$ ($1 \le t \le 10$), the number of test cases. The test cases follow.

The first line of each test case contains three positive integers $n$, $m$, and $k$ ($1 \le n \le 400$, $1 \le k \cdot m \le 400$), separated by single spaces, denoting the number of tasks, participants, and topics respectively. The next $m$ lines each describe one participant. The $i$-th of these lines contains $k$ integers from the interval $[1, 1000]$, separated by single spaces, the skills of the $i$-th participant in every topic. The first of these $m$ lines describes Byteman.

Print $t$ lines to standard output, one per test case. The answer for a test case is TAK (meaning YES) if Byteman has a chance of winning the final round, or NIE (meaning NO) otherwise.

In the first example, one set of tasks that lets Byteman win is: a task from the first topic with difficulty 5, a task from the second topic with difficulty 20, and a task from the third topic with difficulty 75. The final scores are then as follows.

1. Byteman (participant 1): 3 tasks, 170 points
2. Participant 6: 3 tasks, 160 points
3. Participant 4: 3 tasks, 100 points
4. Participant 2: 2 tasks, 360 points
5. Participant 3: 2 tasks, 355 points
6. Participant 5: 2 tasks, 160 points

In the second example, no suitable choice of tasks exists.