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


public class par {
	public static int GROUP = 200;
	
	public static class Car implements Comparable<Car> {
		int num;
		int x;
		int h;
		
		public Car(int num, int x, int h) {
			super();
			this.num = num;
			this.x = x;
			this.h = h;
		}

		@Override
		public int compareTo(Car o) {
			return x - o.x;
		}
		
	}
	
    public static void main(String[] args) throws IOException {
    	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer tokenizer;
    	
    	tokenizer = new StringTokenizer(reader.readLine());
    	int t = Integer.parseInt(tokenizer.nextToken());
    	for(int num = 0; num < t; num++) {
    		boolean res = true;
    		
    		tokenizer = new StringTokenizer(reader.readLine());
        	int n = Integer.parseInt(tokenizer.nextToken());
        	int w = Integer.parseInt(tokenizer.nextToken());
        	
        	Car[] inC = new Car[50000];
        	for(int i = 0; i < n; i++) {
        		tokenizer = new StringTokenizer(reader.readLine());
            	int x1 = Integer.parseInt(tokenizer.nextToken());
            	int y1 = Integer.parseInt(tokenizer.nextToken());
            	int x2 = Integer.parseInt(tokenizer.nextToken());
            	int y2 = Integer.parseInt(tokenizer.nextToken());
        		inC[i] = new Car(i, Math.min(x1, x2), Math.abs(y1 - y2));
        	}
        	Arrays.sort(inC, 0, n);
    		
        	Car[] outC = new Car[50000];
        	for(int i = 0; i < n; i++) {
        		tokenizer = new StringTokenizer(reader.readLine());
            	int x1 = Integer.parseInt(tokenizer.nextToken());
            	int y1 = Integer.parseInt(tokenizer.nextToken());
            	int x2 = Integer.parseInt(tokenizer.nextToken());
            	int y2 = Integer.parseInt(tokenizer.nextToken());
            	outC[i] = new Car(i, Math.min(x1, x2), Math.abs(y1 - y2));
        	}
        	Arrays.sort(outC, 0, n);
        	
        	int[] in = new int[50000];
        	int[] high = new int[50000];
        	int[] highGroup = new int[50000 / GROUP];
        	for(int i = 0; i < highGroup.length; i++) {
        		highGroup[i] = 0;
        	}
        	for(int i = 0; i < high.length; i++) {
        		high[i] = 0;
        	}
        	
        	for(int i = 0; i < n; i++) {
        		in[inC[i].num] = i;
        		high[i] = inC[i].h;
        		int groupNum = i / GROUP;
        		highGroup[groupNum] = Math.max(highGroup[groupNum], inC[i].h);
        	}
        	
        	for(int i = 0; i < n; i++) {
        		int isOnIndex = in[outC[i].num];
        		int highGroupIndex = isOnIndex / GROUP;
        		int myHeight = outC[i].h;
        		for(int j = 0; j < highGroupIndex; j++) {
        			if(highGroup[j] + myHeight > w) {
        				res = false;
        				break;
        			}
        		}
        		for(int j = highGroupIndex * GROUP; j < isOnIndex; j++) {
        			if(high[j] + myHeight > w) {
        				res = false;
        				break;
        			}
        		}
        		if(!res) {
        			break;
        		}
        		if(highGroup[highGroupIndex] == high[isOnIndex]) {
        			high[isOnIndex] = 0;
        			highGroup[highGroupIndex] = 0;
        			int groupStartIndex = highGroupIndex * GROUP;
        			for(int j = 0; j < GROUP; j++) {
        				highGroup[highGroupIndex] = Math.max(highGroup[highGroupIndex], high[groupStartIndex+j]);
        			}
        		}
        		high[isOnIndex] = 0;
        	}
        	
        	System.out.println(res ? "TAK" : "NIE");
    	}
    }
}