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 #include #include #include using namespace std; #define ll long long #define ld long double #define vi vector #define vii vector > #define pb push_back #define pii pair #define mp make_pair #define st first #define nd second #define mini(a,b) a=min(a,(b)) #define maxi(a,b) a=max(a,(b)) #define RE(i,n) for(int i=0,_n=(n);i<_n;++i) #define RI(i,n) for(int i=1,_n=(n);i<=_n;++i) #define h first #define id second const int inf=1e9+5, nax=50123, pot = 64 * 1024; int n, H, odw[nax], tr[2 * pot + 5]; vector > in; vii start, wend; vii parsuj() { RE(i, n) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; in.pb(mp( min(x1, x2), mp(abs(y2 - y1), i) )); } sort(in.begin(), in.end()); vii w; RE(i, in.size()) w.pb(in[i].nd); in.clear(); return w; } bool test() { RE(i, n) tr[pot + i] = wend[i].h; for(int i = pot - 1; i > 0; --i) tr[i] = max(tr[2 * i], tr[2 * i + 1]); RE(i, n) { int cel = odw[start[i].id]; int m = 0; for(int x = pot + cel; x > 0; x /= 2) if(x % 2) maxi(m, tr[x - 1]); if(m + start[i].h > H) return false; tr[pot + cel] = 0; for(int x = (pot + cel) / 2; x > 0; x /= 2) tr[x] = max(tr[2 * x], tr[2 * x + 1]); } return true; } int main() { ios_base::sync_with_stdio(0); int z; cin >> z; while(z--) { cin >> n >> H; start = parsuj(); wend = parsuj(); RE(i, n) odw[wend[i].id] = i; if(test()) cout << "TAK\n"; else cout << "NIE\n"; RE(i, n) tr[pot + i] = 0; } return 0; }