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
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
struct Prostokat{
	int id;
	int x1;
	int y1;
	int x2;
	int y2;
};
int main(){
	ios_base::sync_with_stdio(0);
	int t;
	cin>>t;
	for(int i=0;i<t;i++){
		//tesy
		int n,w;
		cin>>n>>w;
		map<int,int> wysokosci;
		Prostokat polozenie[n];
		for(int j=0;j<n;j++){
		//stare 
			cin>>polozenie[j].x1>>polozenie[j].y1>>polozenie[j].x2>>polozenie[j].y2;
			int wysTemp;
			if(polozenie[j].x1>polozenie[j].x2){ //wyjatek x1>x2
				wysTemp=polozenie[j].x2;
			}else{ //norma x2>=x1
				wysTemp=polozenie[j].x1;
			}
			int doustawienia=abs(polozenie[j].y1-polozenie[j].y2);
			for(int y=wysTemp;y<=abs(polozenie[j].x1-polozenie[j].x2)+wysTemp;y++){
				if(wysokosci.find(y) != wysokosci.end()){
					if(wysokosci[y]<doustawienia){
						wysokosci[y]=doustawienia;
					}
				}else{
				wysokosci[y]=doustawienia;
				}
			}
		}
		Prostokat temp;
		vector<Prostokat> kolejka;
		for(int j=0;j<n;j++){
		//nowe
			cin>>temp.x1>>temp.y1>>temp.x2>>temp.y2;
			temp.id=j;
			if(temp.x1==polozenie[j].x1&&temp.y1==polozenie[j].y1&&temp.x2==polozenie[j].x2&&temp.y2==polozenie[j].y2){
			}else{
				kolejka.push_back(temp);
			}
		}
		//po wczytywaniu ALGORYTM
		bool brejk = false;
		for(int j=0;j<kolejka.size() && !brejk;j++){
			int nie=0;
			int wysokoscPros = abs(kolejka[j].y1-kolejka[j].y2);
			int przodstart,tylstart,kolejkamin,kolejkamax;
			
			if(polozenie[kolejka[j].id].x1>polozenie[kolejka[j].id].x2){
				przodstart=polozenie[kolejka[j].id].x1;
				tylstart=polozenie[kolejka[j].id].x2;
			}else{
				przodstart=polozenie[kolejka[j].id].x2;
				tylstart=polozenie[kolejka[j].id].x1;
			}
			//do kolejki
			if(kolejka[j].x1>kolejka[j].x2){
				kolejkamax=kolejka[j].x1;
				kolejkamin=kolejka[j].x2;
			}else{
				kolejkamax=kolejka[j].x2;
				kolejkamin=kolejka[j].x1;
			}
			if(kolejkamax>przodstart){//przesowamy w przod
				for(int y=przodstart;y<=kolejkamax && !brejk;y++){
					if(wysokosci.find(y) != wysokosci.end()){
						if(w-wysokosci[y]<wysokoscPros){
							nie++;
							if(nie==2){
								cout<<"NIE";
								brejk = true;
							}
						}
					}
				}
			}else{//w tyl albo na miejscu zostaje :)
				for(int y=kolejkamin;y<=tylstart && !brejk;y++){
					if(wysokosci.find(y) != wysokosci.end()){
						if(w-wysokosci[y]<wysokoscPros){
							nie++;
							if(nie==2){
								cout<<"NIE";
								brejk = true;
							}
						}
					}
				}			
			}		
		}
		if(!brejk){
			cout<<"TAK";
		}
		if(i+1!=t){
			cout<<endl;
		}
	}
	return 0;
}