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

/**
 * @author khelman
 */
public class par {

    public static void main(String... args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String s = reader.readLine();
        int t = Integer.parseInt(s);

        big: for (int c = 0; c < t; c++) {
            s = reader.readLine();
            String[] elems = s.split(" ");

            int n = Integer.parseInt(elems[0]);
            int w = Integer.parseInt(elems[1]);

            final int[] sx = new int[n];
            final int[] sy = new int[n];

            final int[] dx = new int[n];
            final int[] dy = new int[n];

            int[] h = new int[n];

            Integer[] si = new Integer[n];
            Integer[] di = new Integer[n];

            int[] sp = new int[n];
            int[] dp = new int[n];

            for (int i = 0; i < n; i++) {
                s = reader.readLine();
                elems = s.split(" ");

                int x1 = Integer.parseInt(elems[0]);
                int y1 = Integer.parseInt(elems[1]);
                int x2 = Integer.parseInt(elems[2]);
                int y2 = Integer.parseInt(elems[3]);

                sx[i] = Math.min(x1, x2);
                sy[i] = Math.min(y1, y2);
                h[i] = Math.abs(y2 - y1);
                si[i] = i;
            }

            for (int i = 0; i < n; i++) {
                s = reader.readLine();
                elems = s.split(" ");

                int x1 = Integer.parseInt(elems[0]);
                int y1 = Integer.parseInt(elems[1]);
                int x2 = Integer.parseInt(elems[2]);
                int y2 = Integer.parseInt(elems[3]);

                dx[i] = Math.min(x1, x2);
                dy[i] = Math.min(y1, y2);
                di[i] = i;
            }

            Arrays.sort(si, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return sx[o1] < sx[o2] ? -1 : (sx[o1] > sx[o2] ? 1 : Integer.compare(sy[o1], sy[o2]));
                }
            });

            Arrays.sort(di, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return dx[o1] < dx[o2] ? -1 : (dx[o1] > dx[o2] ? 1 : Integer.compare(dy[o1], dy[o2]));
                }
            });

            for (int i = 0; i < n; i++) {
                sp[si[i]] = i;
                dp[di[i]] = i;
            }

            for (int i = 0; i < n; i++) { //destination position
                for (int j = 0; j < sp[di[i]]; j++) { //source position
                    //check if they can swap
                    if (dp[si[j]] > i && h[si[j]] + h[di[i]] > w) {
                        System.out.println("NIE");
                        continue big;
                    }
                }

            }

            System.out.println("TAK");
        }
    }

}