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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author Marcin Lewandowski
 */
public class par {

    public static void main(String[] args) throws IOException {
        int t = readInt(System.in);
        rounds:
        for (int round = 0; round < t; round++) {
            int n = readInt(System.in);
            Car[] cars = new Car[n];
            int w = readInt(System.in);
            HashMap<Long, List<Car>> pathsPerXPositions = new HashMap<Long, List<Car>>();
            for (int i = 0; i < n; i++) {
                Car car = new Car(i);
                int x1 = readInt(System.in);
                int y1 = readInt(System.in);
                int x2 = readInt(System.in);
                int y2 = readInt(System.in);
                Point s1 = new Point(Math.min(x1, x2), Math.min(y1, y2));
                Point s2 = new Point(Math.max(x1, x2), Math.max(y1, y2));
                car.s1 = s1;
                car.s2 = s2;
                cars[i] = car;
            }
            for (int i = 0; i < n; i++) {
                int x1 = readInt(System.in);
                int y1 = readInt(System.in);
                int x2 = readInt(System.in);
                int y2 = readInt(System.in);
                Point d1 = new Point(Math.min(x1, x2), Math.min(y1, y2));
                Point d2 = new Point(Math.max(x1, x2), Math.max(y1, y2));
                cars[i].d1 = d1;
                cars[i].d2 = d2;
            }

            for (Car car : cars) {
                long diection = car.d1.x - car.s1.x;
                Path path = null;
                if (diection == 0) {
                    path = new Path(car.d1.x, car.d2.x, 0);
                } else if (diection > 0) {
                    path = new Path(car.s1.x, car.d2.x, 1);
                } else {
                    path = new Path(car.d1.x, car.s2.x, -1);
                }
                car.path = path;
                for (long i = car.path.start; i <= car.path.end; i++) {
                    List<Car> listOfCars = pathsPerXPositions.get(i);
                    if (listOfCars == null) {
                        listOfCars = new ArrayList<Car>();
                        pathsPerXPositions.put(i, listOfCars);
                    }
                    listOfCars.add(car);
                }
            }
            HashSet<Car> toCheck = new HashSet<Car>();
            for (Car car : cars) {
                toCheck.clear();
                if (car.path.dir == 0) {
                    continue;
                }
                for (long i = car.path.start; i <= car.path.end; i++) {
                    List<Car> listOfCars = pathsPerXPositions.get(i);
                    if (listOfCars == null) {
                        continue;
                    }
                    toCheck.addAll(listOfCars);
                }
                toCheck.remove(car);
                for (Car other : toCheck) {
                    if (needToPass(car.path, other.path)) {
                        if (!car.canIPass(other, w)) {
                            System.out.println("NIE");
                            continue rounds;
                        }
                    }
                }
            }
            System.out.println("TAK");
        }
    }

    private static boolean needToPass(Path p1, Path p2) {
        if (p1.dir == 0 && p2.dir == 0) {
            return false;
        } else if (p1.dir != p2.dir) {
            return p1.intersects(p2);
        } else {
            return p1.contains(p2);
        }
    }

    private static int readInt(InputStream in) throws IOException {
        int result = 0;
        boolean isDigit = false;
        int c = 0;
        while ((c = in.read()) != -1) {
            if (c >= '0' && c <= '9') {
                isDigit = true;
                result = result * 10 + c - '0';
            } else if (isDigit) {
                break;
            }
        }
        return result;
    }

    private static class Point {

        public Point(long x, int y) {
            this.x = x;
            this.y = y;
        }
        long x;
        int y;
    }

    private static class Path {

        public Path(long start, long end, int dir) {
            this.start = start;
            this.end = end;
            this.dir = dir;
        }

        public boolean contains(Path p) {
            if (touches(p)) {
                return false;
            }
            if (p.start >= start && p.end <= end) {
                return true;
            }
            return false;
        }

        public boolean intersects(Path p) {
            if (touches(p)) {
                return false;
            }
            if ((p.start >= start && p.start <= end) || ((p.end >= start && p.end <= end))) {
                return true;
            }
            return false;
        }

        public boolean touches(Path p) {
            if (start == p.end || end == p.start) {
                return true;
            }
            return false;
        }
        long start;
        long end;
        int dir;
    }

    private static class Car {

        Point s1;
        Point s2;
        Point d1;
        Point d2;
        Path path;
        final int id;

        public Car(int id) {
            this.id = id;
        }

        public boolean canIPass(Car c, int w) {
            if (c.getHeight() + getHeight() <= w) {
                return true;
            }
            return false;
        }

        public int getHeight() {
            return s2.y - s1.y;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Car other = (Car) obj;
            if (this.id != other.id) {
                return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            int hash = 3;
            hash = 53 * hash + this.id;
            return hash;
        }
    }
}