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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Integer.valueOf;

public class par {

    public static final BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));

    private static class Car {
        int[] startPos = new int[4];
        int[] targetPos = new int[4];

        public int height() {
            return startPos[3] - startPos[1];
        }
    }

    private static void readAndSolve(int n, int maxH) throws IOException {
        Car[] cars = new Car[n];
        for (int i = 0; i < n; i++) {
            cars[i] = new Car();
            cars[i].startPos = readLine();
        }
        for (int i = 0; i < n; i++) {
            cars[i].targetPos = readLine();
        }
        for (int i = 0; i < cars.length; i++) {
            for (int j = 0; j < cars.length; j++) {
                if (i != j) {
                    if (areOverlapping(cars[i].targetPos, cars[j].targetPos)
                            || !(areInTheRightOrder(cars, i, j) || canPass(cars, i, j, maxH))) {
                        System.out.println("NIE");
                        return;
                    }
                }
            }
        }
        System.out.println("TAK");
    }

    private static boolean canPass(Car[] cars, int i, int j, int maxH) {
        return cars[i].height() + cars[j].height() <= maxH;
    }

    private static boolean areInTheRightOrder(Car[] cars, int i, int j) {
        Car c1 = cars[i], c2 = cars[j];
        return !(hasToPass(c1, c2) || hasToPass(c2, c1));
    }

    private static boolean hasToPass(Car c1, Car c2) {
        return c1.startPos[2] <= c2.startPos[0] && c1.targetPos[2] > c2.startPos[0];
    }

    private static boolean areOverlapping(int[] a, int[] b) {
        return isInside(a,b) || isInside(b,a);
    }

    private static boolean isInside(int[] a, int[] b) {
        return ((b[1] < a[1] && a[1] < b[3]) || (b[1] < a[3] && a[3] < b[3]))
                && ((b[0] < a[0] && a[0] < b[2]) || (b[0] < a[2] && a[2] < b[2]));
    }

    private static int[] readLine() throws IOException {
        String oneLine;
        do {
            oneLine = READER.readLine();
        } while ("".equals(oneLine));
        String[] line = oneLine.split(" ");
        int[] result = new int[4];
        for (int i = 0; i < 4; i++) {
            result[i] = valueOf(line[i]);
        }
        int x0 = Math.min(result[0], result[2]);
        int y0 = Math.min(result[1], result[3]);
        int x1 = Math.max(result[0], result[2]);
        int y1 = Math.max(result[1], result[3]);

        result[0] = x0;
        result[1] = y0;
        result[2] = x1;
        result[3] = y1;
        return result;

    }


    public static void main(String[] args) throws IOException {
        int trialsNumber = valueOf(READER.readLine());

        for (int t = 0; t < trialsNumber; t++) {
            String[] line = READER.readLine().split(" ");
            int n = valueOf(line[0]);
            int maxH = valueOf(line[1]);
            readAndSolve(n, maxH);
        }
    }
}