Giải bài trực tuyến

Cuộc thi lập trình sắp tới mà Byteman tham gia sẽ có M thí sinh đánh số từ 1 đến M, Byteman mang số 1. Được biết có N bài toán được chọn, mỗi bài thuộc 1 trong K dạng đã được công bố trước kì thi (nhiều bài có thể thuộc cùng 1 dạng). Dạng bài và độ khó của các bài này đang được ban giám khảo xác định.

Byteman, thay vì luyện tập giải bài, cậu quyết định đi tìm hiểu đối thủ. Cậu biết được các thông số Axy là khả năng của người x tại dạng bài y. Cụ thể, nếu độ khó của 1 bài dạng y được chọn là c:

-   Nếu Axy < c, người x không giải được bài này.

-   Nếu Axy >= c, người x giải được và có Axy – c điểm thưởng. Điểm thưởng cuối cùng của 1 người bằng tổng điểm thưởng có được từ những bài giải được.

-    

Bảng xếp hạng được tính như sau:

-   Người nào giải được nhiều bài hơn sẽ xếp trên

-   Nếu 2 người giải được cùng số bài, người có nhiều điểm thưởng hơn sẽ xếp trên.

Byteman muốn xác định xem liệu có cách lựa chọn bài nào cho phép cậu ta đứng nhất (đồng hạng nhất không tính) trong cuộc thi hay không.

Input:

-   Dòng 1 chứa số T (0 < T <= 10) là số bộ test

-   Với mỗi test, dòng đầu chứa 3 số N, M, K (0 < N <= 400 ; 0 < k.m <= 400)

-   Tiếp đó là M dòng, mỗi dòng chứa K số nguyên mô tả các giá trị Axy (các số nằm trong khoảng [1,1000])

Output :

-   Mỗi test ghi ra 1 dòng : TAK ứng với việc Byteman có thể thắng và NIE nếu không.

Example

TAK

NIE

Một cách lựa chọn cho trường hợp 1 :

3 bài được chọn : dạng 1 với độ khó 5, dạng 2 với độ khó 20 và dạng 3 với độ khó 75.

Bảng xếp hạng :

1. Byteman (#1) : 3 bài, 170 điểm
2. #6 : 3 bài, 160 điểm
3. #4 : 3 bài, 100 điểm
4. #2 : 2 bài, 360 điểm
5. #3 : 2 bài, 355 điểm
6. #5 : 2 bài, 160 điểm