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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NavigableSet;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class par {

	private Integer w;

	public InputStream getInputStream() {
		return System.in;
	}

	public PrintStream getOutputStream() {
		return System.out;
	}

	class Car {
		int x1;
		int y1;
		int x2;
		int y2;
		int h;
		boolean isToMove = false;

		public Car(int x1, int y1, int x2, int y2) {
			this.x1 = x1;
			this.y1 = y1;
			this.x2 = x2;
			this.y2 = y2;
			this.h = y2 - y1;
		}

		public String toString() {
			return "Car [x1=" + x1 + ", y1=" + y1 + ", x2=" + x2 + ", y2=" + y2
					+ "]";
		}

		public boolean isToMove(Car o) {
			if (x1 != o.x1 || x2 != o.x2 || y1 != o.y1 || y2 != o.y2) {
				isToMove = true;
				o.isToMove = true;
				return true;
			}
			return false;
		}

		public boolean collide(Car o) {
			if (x1 >= o.x2) {
				return false;
			}
			if (x2 <= o.x1) {
				return false;
			}
			if (y1 >= o.y2) {
				return false;
			}
			if (y2 <= o.y1) {
				return false;
			}
			return true;
		}
	}

	public void process() {
		BufferedReader reader = null;
		try {
			InputStream in = getInputStream();
			PrintStream out = getOutputStream();
			reader = new BufferedReader(new InputStreamReader(in));
			Integer tests = Integer.valueOf(reader.readLine());
			nextTest: for (int i = 0; i < tests; i++) {
				String line = reader.readLine();
				StringTokenizer tokenizer = new StringTokenizer(line);
				int cars = Integer.valueOf(tokenizer.nextToken());
				w = Integer.valueOf(tokenizer.nextToken());

				// sort all cars that by x1, x2 (closest to (0,0) first)
				Comparator<Car> comp = new Comparator<Car>() {
					public int compare(Car o1, Car o2) {
						if (o1.x1 == o2.x1) {
							return o1.x2 - o2.x2;
						} else {
							return o1.x1 - o2.x1;
						}
					}
				};

				TreeSet<Car> startPos = new TreeSet<Car>(comp);
				LinkedList<Car> startList = new LinkedList<Car>();
				for (int j = 0; j < cars; j++) {
					Car car = readCar(reader);
					startPos.add(car);
					startList.add(car);
				}
				TreeSet<Car> expectedPos = new TreeSet<Car>(comp);
				for (int j = 0; j < cars; j++) {
					Car newCar = readCar(reader);
					Car oldCar = startList.remove();
					if (oldCar.isToMove(newCar)) {
						expectedPos.add(newCar);
					} else {
						expectedPos.add(oldCar);
					}
				}

				TreeSet<Car> alreadyPlaced = new TreeSet<Car>(comp);
				// start moving cars
				Car carToMove = expectedPos.pollFirst();
				while (carToMove != null) {
					// remove from already placed all cars that are already in
					// front of it(they does not matter anymore)
					for (Iterator<Car> iterator = alreadyPlaced.iterator(); iterator
							.hasNext();) {
						Car car = iterator.next();
						if (car.x2 < carToMove.x1) {
							iterator.remove();
						}
					}

					if (carToMove.isToMove) {
						// check if move is possible
						// get list of cars to pass
						NavigableSet<Car> carsToPass = startPos.headSet(
								carToMove, false);
						// find out the the widest cars to pass
						int maxH = 0;
						for (Car car : carsToPass) {
							maxH = Math.max(maxH, car.h);
						}
						int availableH = w - maxH;
						if (availableH < carToMove.h) {
							out.println("NIE");
							break nextTest;
						}
					}

					// check collisions with already placed cars
					for (Iterator<Car> iterator = alreadyPlaced.iterator(); iterator
							.hasNext();) {
						Car car = iterator.next();
						if (car.collide(carToMove)) {
							out.println("NIE");
							break nextTest;
						}
					}
					alreadyPlaced.add(carToMove);
					carToMove = expectedPos.pollFirst();
				}
				out.println("TAK");
			}
		} catch (Throwable t) {
			t.printStackTrace();
		} finally {
			if (reader != null) {
				try {
					reader.close();
				} catch (Throwable t) {
					t.printStackTrace();
				}
			}
		}
	}

	private Car readCar(BufferedReader reader) throws IOException {
		String line = reader.readLine();
		StringTokenizer tokenizer = new StringTokenizer(line);
		int x1 = Integer.valueOf(tokenizer.nextToken());
		int y1 = Integer.valueOf(tokenizer.nextToken());
		int x2 = Integer.valueOf(tokenizer.nextToken());
		int y2 = Integer.valueOf(tokenizer.nextToken());
		return new Car(x1, y1, x2, y2);
	}

	public static void main(String[] args) {
		par par = new par();
		par.process();
	}
}