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 #include #include using namespace std; struct Samochod { int m, n, w, x; } A[50000], B[50000]; bool operator< (Samochod a, Samochod b) { if (a.x == b.x) return a.w < b.w; else return a.x < b.x; } int n, w, I[50000]; bool scal(int a, int b, int c) { int i = a, j = b, k = 0, m = 0; while (i < b && j < c) { if (A[i].n < A[j].n) { B[k++] = A[i++]; } else { if (A[j].w + A[i].m > w) { return false; } B[k++] = A[j++]; } } while (i < b) B[k++] = A[i++]; while (j < c) B[k++] = A[j++]; for (i = 0, j = a; i < k; ++i, ++j) A[j] = B[i]; for (i = c - 1; i >= a; --i) { if (A[i].w > m) m = A[i].w; A[i].m = m; } return true; } bool sortuj() { for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j += i << 1) { if (!scal(j, min(j + i, n), min(j + i + i, n))) return false; } } return true; } int main() { int t, x1, x2, y1, y2; scanf("%d", &t); while (t--) { scanf("%d %d", &n, &w); for (int i = 0; i < n; ++i) { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); A[i].n = i; A[i].m = A[i].w = max(y1, y2) - min(y1, y2); A[i].x = min(x1, x2); } sort(A, A + n); for (int i = 0; i < n; ++i) I[A[i].n] = i; for (int i = 0; i < n; ++i) { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); B[i].n = i; B[i].w = max(y1, y2) - min(y1, y2); B[i].x = min(x1, x2); } sort(B, B + n); for (int i = 0; i < n; ++i) A[I[B[i].n]].n = i; puts(sortuj() ? "TAK" : "NIE"); } return 0; }