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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// Grzegorz Chuchro

#include <stdio.h>
unsigned int w_min[100000], w_max[100000], h_min[100000], h_max[100000];

unsigned int w_shortest, w_highest, h_shortest, h_highest;
unsigned int w_shortest_indexes[100000], h_shortest_indexes[100000];
unsigned int w_shortest_indexes_size, w_highest_indexes_size, h_shortest_indexes_size, h_highest_indexes_size;

unsigned int w_shortest_and_highest_indexes[100000], h_shortest_and_highest_indexes[100000];
unsigned int w_shortest_and_highest_indexes_size, h_shortest_and_highest_indexes_size;

int main(){
	int t;
	int n;
	int i, j;
	int error;
	
	scanf("%d", &t);
	
	while(t--){
		
		scanf("%d", &n);
		
		i = n;		
		while(i--) scanf("%u%u%u%u", &w_min[i], &w_max[i], &h_min[i], &h_max[i]);
		
		// check width
		////////////////////////////////////////////////////////////////
		
		// get indexes of shortest width
		w_shortest = w_min[n-1];
		w_shortest_indexes[0] = n-1;
		w_shortest_indexes_size = 1;
		i = n-1;		
		while(i--){
			if(w_min[i]<=w_shortest){
				if(w_min[i]<w_shortest){
					w_shortest = w_min[i];
					w_shortest_indexes[0] = i;
					w_shortest_indexes_size = 1;
				} else w_shortest_indexes[w_shortest_indexes_size++] = i; // is equal case
			}
		}
		
		// get highest width value
		w_highest = w_max[n-1];
		i = n-1;		
		while(i--) if(w_max[i]>w_highest) w_highest = w_max[i];
		
		// get indexes that have both shortest and highest width at the same time
		w_shortest_and_highest_indexes_size = 0;
		i = w_shortest_indexes_size;
		while(i--) if(w_max[w_shortest_indexes[i]]==w_highest) w_shortest_and_highest_indexes[w_shortest_and_highest_indexes_size++] =  w_shortest_indexes[i]; // can't be higher than highest
		
		// check if error
		if(w_shortest_and_highest_indexes_size==0){
			puts("NIE");
			continue;
		}
		
		// check height (in the same way)
		//@ could be a function
		////////////////////////////////////////////////////////////////
		
		// get indexes of shortest height
		h_shortest = h_min[n-1];
		h_shortest_indexes[0] = n-1;
		h_shortest_indexes_size = 1;
		i = n-1;		
		while(i--){
			if(h_min[i]<=h_shortest){
				if(h_min[i]<h_shortest){
					h_shortest = h_min[i];
					h_shortest_indexes[0] = i;
					h_shortest_indexes_size = 1;
				} else h_shortest_indexes[h_shortest_indexes_size++] = i; // is equal case
			}
		}
		
		// get highest height value
		h_highest = h_max[n-1];
		i = n-1;		
		while(i--) if(h_max[i]>h_highest) h_highest = h_max[i];
		
		// get indexes that have both shortest and highest height at the same time
		h_shortest_and_highest_indexes_size = 0;
		i = h_shortest_indexes_size;
		while(i--) if(h_max[h_shortest_indexes[i]]==h_highest) h_shortest_and_highest_indexes[h_shortest_and_highest_indexes_size++] =  h_shortest_indexes[i]; // can't be higher than highest
	
		// check if error
		if(h_shortest_and_highest_indexes_size==0){
			puts("NIE");
			continue;
		}
		
		/*i = w_shortest_and_highest_indexes_size;
		while(i--) printf("%d ", w_shortest_and_highest_indexes[i]);
		int k=1000;while(k--)puts("");
		i = h_shortest_and_highest_indexes_size;
		while(i--) printf("%d ", h_shortest_and_highest_indexes[i]);
		puts("");*/
		
		// check if w_shortest_and_highest_indexes and h_shortest_and_highest_indexes share any elements
		// indexes are sorted
		////////////////////////////////////////////////////////////////
		i = w_shortest_and_highest_indexes_size-1;
		j = h_shortest_and_highest_indexes_size-1;
		//printf("%d %d %d %d\n",w_shortest_and_highest_indexes[i],h_shortest_and_highest_indexes[j], i, j);
		if(w_shortest_and_highest_indexes[0]>h_shortest_and_highest_indexes[j] || w_shortest_and_highest_indexes[i]<h_shortest_and_highest_indexes[0]){
			puts("NIE");
			continue;
		} else{
			error = 1;
			do{
				while(w_shortest_and_highest_indexes[i]<h_shortest_and_highest_indexes[j]) --j;
				while(w_shortest_and_highest_indexes[i]>h_shortest_and_highest_indexes[j]) --i;
				if(w_shortest_and_highest_indexes[i]==h_shortest_and_highest_indexes[j]){
					puts("TAK");
					error = 0;
					break;
				}
			} while(i>0 && j>0);
			
			//printf("%d %d %d %d\n",w_shortest_and_highest_indexes[i],h_shortest_and_highest_indexes[j], i, j);
			if(error==1) puts("NIE");
		}
	}
	
	return 0;
}