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
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
const int inf=1e9+7;
vector<int>Wx,Wn,Hx,Hn,Wgood,Hgood;
int Wmax,Wmin,Hmax,Hmin,n;
bool solve()
{
    int a,b,c,d;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(a<Wmin)
        {
            Wmin=a;
            Wn.clear();
            Wn.push_back(i);
        }
        else if(Wmin==a)Wn.push_back(i);
        if(b>Wmax)
        {
            Wmax=b;
            Wx.clear();
            Wx.push_back(i);
        }
        else if(Wmax==b)Wx.push_back(i);

        if(c<Hmin)
        {
            Hmin=c;
            Hn.clear();
            Hn.push_back(i);
        }
        else if(Hmin==c)Hn.push_back(i);
        if(d>Hmax)
        {
            Hmax=d;
            Hx.clear();
            Hx.push_back(i);
        }
        else if(Hmax==d)Hx.push_back(i);
    }
	int i=0,j=0;
	for(i=0;i<Wn.size() && j<Wx.size();i++)
	{
		while(j<Wx.size() && Wx[j]<Wn[i])j++;
		if(j<Wx.size() && Wx[j]==Wn[i])Wgood.push_back(Wx[j]);
	}
	i=j=0;
	for(i=0;i<Hn.size() && j<Hx.size();i++)
	{
		while(j<Hx.size() && Hx[j]<Hn[i])j++;
		if(j<Hx.size() && Hx[j]==Hn[i])Hgood.push_back(Hx[j]);
	}
	i=j=0;
	for(i=0;i<Wgood.size() && j<Hgood.size();i++)
	{
		while(j<Hgood.size() && Hgood[j]<Wgood[i])j++;
		if(j<Hgood.size() && Hgood[j]==Wgood[i])return true;
	}
	return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
		Wn.clear();
		Wx.clear();
		Hx.clear();
		Hn.clear();
		Wgood.clear();
		Hgood.clear();
        Wmax=0;
        Wmin=inf;
        Hmax=0;
        Hmin=inf;
        scanf("%d",&n);
        if(solve())printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}