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 #include #include #include #include using namespace std; struct prostokat { int x; int h; int id; }; bool cmp1(prostokat a, prostokat b) { return a.x < b.x; } const int m = 65536; int dr[2 * m + 1]; int wh[m]; void insert(int x, int w) { x += m; dr[x] = w; x /= 2; while(x > 0) { dr[x] = max(dr[2 * x], dr[2 * x + 1]); x /= 2; } } int query(int a, int b) { if(b < a) return 0; a += m; b += m; int w = max(dr[a], dr[b]); while(a / 2 != b / 2) { if(a % 2 == 0) w = max(w, dr[a + 1]); if(b % 2 == 1) w = max(w, dr[b - 1]); a /= 2; b /= 2; } return w; } int main() { ios_base::sync_with_stdio(0); int prz; cin >> prz; for(int licz = 0; licz < prz; ++licz) { int n, w; cin >> n >> w; vector t(n); int a, b, c, d; for(int i = 0; i < n; ++i) { cin >> a >> b >> c >> d; t[i].x = min(a, c); t[i].h = abs(b - d); t[i].id = i; } sort(t.begin(), t.end(), cmp1); for(int i = 0; i < n; ++i) wh[t[i].id] = i; vector goal(n); for(int i = 0; i < n; ++i) { cin >> a >> b >> c >> d; goal[i].x = min(a, c); goal[i].h = abs(b - d); goal[i].id = i; } sort(goal.begin(), goal.end(), cmp1); for(int i = 0; i < n; ++i) dr[i + m] = t[i].h; for(int i = m - 1; i >= 1; --i) dr[i] = max(dr[2 * i], dr[2 * i + 1]); int wynik = 1; for(int i = 0; i < n; ++i) { if(goal[i].h + query(0, wh[goal[i].id] - 1) > w) wynik = 0; insert(wh[goal[i].id], 0); } if(wynik) cout << "TAK\n"; else cout << "NIE\n"; } return 0; }