1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdlib.h>

int* p;
int** r;

int check(int n, int d) {
    int i;
    int z1, z2, z3, z4;
    z1 = r[0][n];
    z2 = r[1][n];
    z3 = r[2][n];
    z4 = r[3][n];
    for(i=0; i<d; i++) {
        if(r[0][i] < z1) return 0;
        if(r[1][i] > z2) return 0;
        if(r[2][i] < z3) return 0;
        if(r[3][i] > z4) return 0;
    }
    return 1;
}

int findMin(int j, int coord) {
        int min = r[coord][0];
        int k = 1, i;
        for(i=1; i<j; i++) {
            if(r[coord][p[i]] < min) {
                min = r[coord][p[i]];
                k = 1;
                p[0] = p[i];
            }
            else if(r[coord][p[i]] == min) {
                p[k] = p[i];
                k++;
            }
        }
        return k;
}

int findMax(int j, int coord) {
        int max = r[coord][0];
        int k = 1, i;
        for(i=1; i<j; i++) {
            if(r[coord][p[i]] > max) {
                max = r[coord][p[i]];
                k = 1;
                p[0] = p[i];
            }
            else if(r[coord][p[i]] == max) {
                p[k] = p[i];
                k++;
            }
        }
        return k;
}

int main() {
    int t, d, i;
    scanf("%d", &t);
    while(t--) {
        scanf("%d",&d);
        r = (int**)malloc(4 * sizeof(int*));
        for(i=0; i<4; i++)
            r[i] = (int*)malloc(d * sizeof(int));
        for(i=0; i<d; i++) {
           scanf("%d", &(r[0][i]));
           scanf("%d", &(r[1][i]));
           scanf("%d", &(r[2][i]));
           scanf("%d", &(r[3][i]));
        }
        p = (int*)malloc(d * sizeof(int));
        int min, j;
        min = r[0][0];
        j = 1;
        p[0] = 0;
        for(i=1; i<d; i++) {
            if(r[0][i] < min) {
                min = r[0][i];
                j = 1;
                p[0] = i;
            }
            else if(r[0][i] == min) {
                p[j] = i;
                j++;
            }
        }
        j = findMax(j, 1);
        j = findMin(j, 2);
        j = findMax(j, 3);
        if(check(p[0], d))
            printf("TAK\n");
        else printf("NIE\n");
        for(i=0; i<4; i++)
            free(r[i]);
        free(r);
        free(p);
    }
	return 0;
}