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
import java.awt.Point;
import java.io.BufferedInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class par {
	static Samochod maxWysoki = new Samochod(-1, 0, 0, 0, 0);
	static ArrayList<Samochod> listaSamochodow = new ArrayList<Samochod>();
	static int wysokoscParkinguK = 0;

	public static void main(String[] args) throws FileNotFoundException {

		Scanner odczyt = new Scanner(new BufferedInputStream(System.in));
		int iloscTestow = odczyt.nextInt();
		for (int test = 0; test < iloscTestow; test++) {
			int iloscSamochodow = odczyt.nextInt();
			int wysokoscParkingu = odczyt.nextInt();
			wysokoscParkinguK = wysokoscParkingu;
			listaSamochodow.clear();
			for (int i = 0; i < iloscSamochodow; i++) {
				int x1 = odczyt.nextInt();
				int y1 = odczyt.nextInt();
				int x2 = odczyt.nextInt();
				int y2 = odczyt.nextInt();
				Samochod samochod = new Samochod(i, x1, y1, x2, y2);
				listaSamochodow.add(samochod);
				if (maxWysoki.wysokoscSamochodu() < samochod.wysokoscSamochodu())
					maxWysoki = samochod;
			}

			boolean czyWszystkoDobrze = true;
			for (int i = 0; i < iloscSamochodow; i++) {
				int x1 = odczyt.nextInt();
				int y1 = odczyt.nextInt();
				int x2 = odczyt.nextInt();
				int y2 = odczyt.nextInt();
				Samochod samochod = new Samochod(i, x1, y1, x2, y2);
				if (czyWszystkoDobrze && !czyDasieTamPrzeniesc(samochod)) {
					czyWszystkoDobrze = false;
				}

			}
			if (czyWszystkoDobrze)
				System.out.println("TAK");
			else
				System.out.println("NIE");
		}
		odczyt.close();
	}

	static boolean czyDasieTamPrzeniesc(Samochod docelowe) {
		Samochod pierwotne = listaSamochodow.get(docelowe.id);
		if (docelowe.czyTaSamaPozycja(pierwotne))
			return true;
		boolean czyMogloByMaxPrzeszkodzic = pierwotne.czyMogloByPrzeszkazac(docelowe, maxWysoki);
		if (czyMogloByMaxPrzeszkodzic){
			if ((wysokoscParkinguK - maxWysoki.wysokoscSamochodu()) < docelowe.wysokoscSamochodu()
				&& docelowe.id != maxWysoki.id)
				return false;
		}
		else{
			for (Samochod s : listaSamochodow) {
				int maxWysokosc = wysokoscParkinguK - s.wysokoscSamochodu();
				if (docelowe.wysokoscSamochodu() > maxWysokosc && docelowe.id != s.id
					&& pierwotne.czyMogloByPrzeszkazac(docelowe, s)) {
					return false;
				}
			}		
		}
		return true;
	}
}

class Samochod {
	int id;
	Point ld = null;
	Point pg = null;

	Samochod(int id, int x1, int y1, int x2, int y2) {
		this.id = id;
		this.ld = new Point(x1, y1);
		this.pg = new Point(x2, y2);
	}

	int wysokoscSamochodu() {
		return Math.abs(pg.y - ld.y);
	}

	boolean czyTaSamaPozycja(Samochod docelowe) {
		return ld.equals(docelowe.ld) && pg.equals(docelowe.pg);
	}

	boolean czyMogloByPrzeszkazac(Samochod docelowe, Samochod przeszkoda) {
		if (czyTaSamaPozycja(docelowe))
			return false;
		boolean czyWPrawo = docelowe.pg.x > pg.x;
		if (czyWPrawo) {
			return pg.x <= przeszkoda.pg.x && przeszkoda.pg.x <= docelowe.pg.x;
		}
		else {
			return docelowe.pg.x <= przeszkoda.pg.x && przeszkoda.pg.x <= pg.x;
		}
	}

}