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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;


public class par {
	
	public static class Car {
		
		private int x0;
		private int x1;
		private int y0;
		private int y1;
		
		private int xDiff;
		private int yDiff;
		
		private int maxDiff;
		
		private int index;
		private int indexRev;
		private int parkingIndex;

		public Car(int x0, int y0, int x1, int y1, int index) {
			this.x0 = Math.min(x0, x1);
			this.x1 = Math.max(x0, x1);
			this.y0 = Math.min(y0, y1);
			this.y1 = Math.max(y0, y1);
			xDiff = x1 - x0;
			yDiff = y1 - y0;
			this.index = index;
			this.parkingIndex = -1;
			this.indexRev = -1;
			this.maxDiff = 0;
		}

		public int getX0() {
			return x0;
		}

		public int getX1() {
			return x1;
		}

		public int getY0() {
			return y0;
		}

		public int getY1() {
			return y1;
		}

		public int getXDiff() {
			return xDiff;
		}

		public int getYDiff() {
			return yDiff;
		}

		public int getIndex() {
			return index;
		}
		
		public void setIndex(int index) {
			this.index = index;
		}

		public int getParkingIndex() {
			return parkingIndex;
		}

		public void setParkingIndex(int parkingIndex) {
			this.parkingIndex = parkingIndex;
		}

		public int getIndexRev() {
			return indexRev;
		}

		public void setIndexRev(int indexRev) {
			this.indexRev = indexRev;
		}
		
		public int getMaxDiff() {
			return maxDiff;
		}

		public void setMaxDiff(int maxDiff) {
			this.maxDiff = maxDiff;
		}

		@Override
		public String toString() {
			return "[(" + x0 + "," + y0 + ") (" + x1  + "," + y1
					+ ") (" + xDiff + "," + yDiff + "," + maxDiff + ") i=" 
					+ index + " ir=" + indexRev + " pi=" + parkingIndex + "]";
		}
		
	}
	
	public static class CarX0ComparatorAsc implements Comparator<Car> {
		@Override
		public int compare(Car arg0, Car arg1) {
			return Integer.compare(arg0.getX0(), arg1.getX0());
		}
		
	}
	
	public static class CarYDiffComparatorAsc implements Comparator<Car> {
		@Override
		public int compare(Car arg0, Car arg1) {
			return Integer.compare(arg0.getYDiff(), arg1.getYDiff());
		}
		
	}
	
	public static class CarParkingIndexComparatorAsc implements Comparator<Car> {
		@Override
		public int compare(Car arg0, Car arg1) {
			return Integer.compare(arg0.getParkingIndex(), arg1.getParkingIndex());
		}
		
	}

	public static void main(String[] args) {
		try{
			BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
			int t = Integer.parseInt(buffReader.readLine());
			for(int test=0; test<t; test++){	
				StringTokenizer tokenizer = new StringTokenizer(buffReader.readLine());
				int n = Integer.parseInt(tokenizer.nextToken());
				int w = Integer.parseInt(tokenizer.nextToken());
				Car[] carPositions = new Car[n];
				Car[] parkingPositions = new Car[n];
				for (int i=0; i<n; i++){
					tokenizer = new StringTokenizer(buffReader.readLine());
					carPositions[i] = new Car(Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()), i);
				}
				for (int i=0; i<n; i++){
					tokenizer = new StringTokenizer(buffReader.readLine());
					parkingPositions[i] = new Car(Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()), i);
				}
				
				Arrays.sort(parkingPositions, new CarX0ComparatorAsc());
				for (int i=0; i<n; i++)
					carPositions[parkingPositions[i].getIndex()].setParkingIndex(i); 
				Arrays.sort(carPositions, new CarX0ComparatorAsc());
				int[] carParkingOrder = new int[n];
				for (int i=0; i<n; i++)
					carParkingOrder[carPositions[i].getParkingIndex()] = i;
				carPositions[0].setIndex(-1);
				carPositions[0].setIndexRev(1);
				carPositions[0].setMaxDiff(carPositions[0].getYDiff());
				for (int i=1; i<n-1; i++){
					carPositions[i].setIndex(i-1);
					carPositions[i].setIndexRev(i+1);
					carPositions[i].setMaxDiff(Math.max(carPositions[i-1].getMaxDiff(), carPositions[i].getYDiff()));
				}
				carPositions[n-1].setIndex(n-2);
				carPositions[n-1].setIndexRev(n);
				carPositions[n-1].setMaxDiff(Math.max(carPositions[n-2].getMaxDiff(), carPositions[n-1].getYDiff()));
				
				int i = 0;
				boolean noBlock = true;
				while(i<n && noBlock){
					Car parkingCar = carPositions[carParkingOrder[i]];
					Car testCar = parkingCar;
					if(carPositions[Math.max(0,carParkingOrder[i]-1)].getMaxDiff() + testCar.getYDiff() > w)
					while(testCar.getIndex() >= 0 && noBlock){
						testCar = carPositions[testCar.getIndex()];
						if(parkingCar.getYDiff() + testCar.getYDiff() > w && parkingCar.getParkingIndex() < testCar.getParkingIndex()){
							noBlock = false;
						}
					}
					if(parkingCar.getIndex() >= 0){
						testCar = carPositions[parkingCar.getIndex()];
						testCar.setIndexRev(parkingCar.getIndexRev());
					}
					if(parkingCar.getIndexRev() < n){
						testCar = carPositions[parkingCar.getIndexRev()];
						testCar.setIndex(parkingCar.getIndex());
					}
					i++;
				}
				System.out.println(noBlock ? "TAK" : "NIE");
				
			}
		}catch(Exception e){
			e.printStackTrace();
		}
		
	}

}