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
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
#include <functional>
#include <initializer_list>

template<class Containers >
bool set_intersection_not_empty( std::initializer_list< Containers > ilist )
{
    if(ilist.size() == 0) return false;
    std::vector< typename Containers::const_iterator > firsts;
    std::vector< typename Containers::const_iterator > lasts;
    firsts.reserve(ilist.size());
    lasts.reserve(ilist.size());
    for( Containers const& c: ilist  )
    {
        firsts.push_back( c.begin() );
        lasts.push_back( c.end() );
        if( firsts.back() == lasts.back() ) return false;
    }
    typename Containers::value_type vmin = *(firsts[0]);
    for( int i=1,s=ilist.size(); i < s; ++i )
    {
        typename Containers::value_type v= *(firsts[i]);
        while( v < vmin ) // TODO: zastapic przez LowerBound dla seta i vectora?
        {
            if(++firsts[i] == lasts[i])
                return false;
            v= *(firsts[i]);
        }
        if( vmin == v )
            continue;
        vmin=v;
        i=-1;
    }
    return true;
}


template< class Container, class Compare >
void insertIf( int id, int val, int &valmin,  Container& set, Compare comp )
{
    if( comp( valmin, val ) ) return;
    if( comp( val, valmin ) )
    {
        set.clear();
        valmin = val;
    }
    set.insert(set.begin(),id);
}


int main()
{
    int n;
    std::cin >> n;
    while(n--)
    {
        int s;
        std::cin >> s;
        std::deque<int> sW1,sW2,sH1,sH2; // deque, set or list
        sW1.insert( sW1.begin(), s );
        sW2.insert( sW2.begin(), s );
        sH1.insert( sH1.begin(), s );
        sH2.insert( sH2.begin(), s );
        int w1min,w2max,h1min,h2max;
        std::cin >> w1min >> w2max >> h1min >> h2max;
        while(--s)
        {
            int val;
            std::cin >> val;
            insertIf(s,val,w1min,sW1,std::less<int>());
            std::cin >> val;
            insertIf(s,val,w2max,sW2,std::greater<int>());
            std::cin >> val;
            insertIf(s,val,h1min,sH1,std::less<int>());
            std::cin >> val;
            insertIf(s,val,h2max,sH2,std::greater<int>());
        }
        if( set_intersection_not_empty( { sW1,sW2,sH1,sH2 }  ) )
            std::cout << "TAK" << std::endl;
        else
            std::cout << "NIE" << std::endl;

    }
    return 0;
}