#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Point{
	Point(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}

	Point(){
		x = y = 0.0;
	}

	Point operator + (Point p){ return Point(x+p.x,y+p.y); }
	Point operator - (Point p){ return Point(x-p.x,y-p.y);}
	Point operator * (double a){ return Point(a*x,a*y); }
	Point operator / (double a){ return Point(x/a,y/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator<(const Point &p) const{
		return x != p.x? x < p.x: y < p.y;
	}

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
	}

	double x,y;
};
typedef Point Vector;

struct Circle{
	Point center;
	double r;
};

struct Line{
	Point p[2];
	Line(Point p1,Point p2){
		p[0] = p1;
		p[1] = p2;
		diff = 0;
	}
	Line(){
		diff = 0;
	}
	double diff;
};

int N;
double W,H,R;
vector<Line> WALL,LINE,CIRCLE_WALL,CIRCLE_LINE[105];

double norm(Vector a){
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a){
	return sqrt(norm(a));
}

double cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}

double dot(Vector a,Vector b){
    return a.x*b.x + a.y*b.y;
}


//交点を求める関数
Point calc_Cross_Point(double x1,double x2,double x3,double x4,double y1,double y2,double y3,double y4){
	Point ret;
	ret.x = ((x2-x1)*(y3*(x4-x3)+x3*(y3-y4))-(x4-x3)*(y1*(x2-x1)+x1*(y1-y2)))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
	if(x1 != x2){
		ret.y = ((y2-y1)*ret.x+y1*(x2-x1)+x1*(y1-y2))/(x2-x1);
	}else{
		ret.y = ((y4-y3)*ret.x+y3*(x4-x3)+x3*(y3-y4))/(x4-x3);
	}
	return ret;
}

//インタフェース関数
Point calc_Cross_Point(Point a,Point b,Point c,Point d){
	return calc_Cross_Point(a.x,b.x,c.x,d.x,a.y,b.y,c.y,d.y);
}

Point calc_Cross_Point(Line A,Line B){

	return calc_Cross_Point(A.p[0],A.p[1],B.p[0],B.p[1]);
}

Point calc_minus(Point a,Point b){
    Point ret;

    ret.x = a.x-b.x;
    ret.y = a.y-b.y;

    return ret;
}

double calc_len(Vector a){
    return sqrt(a.x*a.x+a.y*a.y);
}

//点と直線の距離(ただし、直線が無限長)
double calc_dist1(Line line,Point point){
    return abs(cross(line.p[1]-line.p[0],point-line.p[0]))/abs(line.p[1]-line.p[0]);
}

bool rangeCheck(Point point){

	return point.x >= R-EPS && point.x <= W-R+EPS && point.y >= R-EPS && point.y <= H-R+EPS;
}

bool is_OK(Point cross_point){

	if(!rangeCheck(cross_point))return false;

	//警告線と交差していないか調べる
	for(int c = 0; c < N; c++){

		double tmp_dist =  calc_dist1(LINE[c],cross_point);

		if(tmp_dist+EPS < R+LINE[c].diff){

			return false;
		}
	}

	//壁と交差していないか調べる
	for(int c = 0; c < 4; c++){

		double tmp_dist =  calc_dist1(WALL[c],cross_point);

		if(tmp_dist+EPS < R){

			return false;
		}
	}

	return true;
}


double calc_slope(Line A){

	if(fabs(A.p[0].x-A.p[1].x) < EPS){

		return DBL_MAX;

	}else if(fabs(A.p[0].y-A.p[1].y) < EPS){

		return 0;

	}else{

		return (A.p[0].y-A.p[1].y)/(A.p[0].x-A.p[1].x);
	}
}

bool is_Cross(Line A,Line B){

	return fabs(calc_slope(A)-calc_slope(B)) > EPS;
}

void func(){

	WALL.clear();
	LINE.clear();
	CIRCLE_WALL.clear();

	for(int i = 0; i < N; i++){

		CIRCLE_LINE[i].clear();
	}

	WALL.push_back(Line(Point(0,H),Point(0,0)));
	WALL.push_back(Line(Point(0,0),Point(W,0)));
	WALL.push_back(Line(Point(W,0),Point(W,H)));
	WALL.push_back(Line(Point(W,H),Point(0,H)));

	CIRCLE_WALL.push_back(Line(Point(R,H),Point(R,0)));
	CIRCLE_WALL.push_back(Line(Point(0,R),Point(W,R)));
	CIRCLE_WALL.push_back(Line(Point(W-R,0),Point(W-R,H)));
	CIRCLE_WALL.push_back(Line(Point(W,H-R),Point(0,H-R)));

	double diff;

	for(int i = 0; i < N; i++){

		Line tmp_line;

		scanf("%lf %lf %lf %lf %lf",&tmp_line.p[0].x,&tmp_line.p[0].y,&tmp_line.p[1].x,&tmp_line.p[1].y,&tmp_line.diff);
		LINE.push_back(tmp_line);

		//円を求めるため、平行移動した直線をあらかじめ求めておく

		Line top_line,under_line;

		if(fabs(tmp_line.p[0].x-tmp_line.p[1].x) < EPS){ //垂直な線分

			diff = tmp_line.diff+R;

			//p_top,p_underの設定
			top_line.p[0].x = tmp_line.p[0].x+diff;
			top_line.p[0].y = tmp_line.p[0].y;
			top_line.p[1].x = tmp_line.p[1].x+diff;
			top_line.p[1].y = tmp_line.p[1].y;

			CIRCLE_LINE[i].push_back(top_line);

			under_line.p[0].x = tmp_line.p[0].x-diff;
			under_line.p[0].y = tmp_line.p[0].y;
			under_line.p[1].x = tmp_line.p[1].x-diff;
			under_line.p[1].y = tmp_line.p[1].y;

			CIRCLE_LINE[i].push_back(under_line);

		}else{

			double slope = (tmp_line.p[1].y-tmp_line.p[0].y)/(tmp_line.p[1].x-tmp_line.p[0].x);

			diff = sqrt(slope*slope+1)*(R+tmp_line.diff);

			//p_top,p_underの設定
			top_line.p[0].x = tmp_line.p[0].x;
			top_line.p[0].y = tmp_line.p[0].y+diff;
			top_line.p[1].x = tmp_line.p[1].x;
			top_line.p[1].y = tmp_line.p[1].y+diff;

			CIRCLE_LINE[i].push_back(top_line);

			under_line.p[0].x = tmp_line.p[0].x;
			under_line.p[0].y = tmp_line.p[0].y-diff;
			under_line.p[1].x = tmp_line.p[1].x;
			under_line.p[1].y = tmp_line.p[1].y-diff;

			CIRCLE_LINE[i].push_back(under_line);
		}
	}

	//任意の2つの警告線について試す
	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			if(k == i)continue;

			for(int a = 0; a < 2; a++){
				for(int b = 0; b < 2; b++){

					if(!is_Cross(CIRCLE_LINE[i][a],CIRCLE_LINE[k][b]))continue;

					Point cross_point = calc_Cross_Point(CIRCLE_LINE[i][a],CIRCLE_LINE[k][b]);

					if(is_OK(cross_point)){

						printf("Yes\n");
						return;
					}
				}
			}
		}
	}


	//壁と壁
	for(int i = 0; i < 3; i++){
		for(int k = i+1; k < 4; k++){

			if(!is_Cross(CIRCLE_WALL[i],CIRCLE_WALL[k]))continue;

			Point cross_point = calc_Cross_Point(CIRCLE_WALL[i],CIRCLE_WALL[k]);

			if(is_OK(cross_point)){

				printf("Yes\n");
				return;
			}
		}
	}

	//任意の壁と、1つの警告線について試す
	for(int i = 0; i < 4; i++){
		for(int k = 0; k < N; k++){
			for(int a = 0; a < 2; a++){

				if(!is_Cross(CIRCLE_WALL[i],CIRCLE_LINE[k][a]))continue;

				Point cross_point = calc_Cross_Point(CIRCLE_WALL[i],CIRCLE_LINE[k][a]);

				if(is_OK(cross_point)){

					printf("Yes\n");
					return;
				}
			}
		}
	}

	printf("No\n");
}

int main(){

	int input_W,input_H,input_R;

	while(true){

		scanf("%d %d %d %d",&input_W,&input_H,&N,&input_R);
		if(input_W == 0 && input_H == 0 && N == 0 && input_R == 0)break;

		W = input_W,H = input_H,R = input_R;

		func();

	}

	return 0;
}


### Prompt

Construct a Cpp code solution to the problem outlined:

Nathan O. Davis is challenging a kind of shooter game. In this game, enemies emit laser beams from outside of the screen. A laser beam is a straight line with a certain thickness. Nathan moves a circular-shaped machine within the screen, in such a way it does not overlap a laser beam. As in many shooters, the machine is destroyed when the overlap happens.

Nathan is facing an uphill stage. Many enemies attack simultaneously in this stage, so eventually laser beams fill out almost all of the screen. Surprisingly, it is even possible he has no "safe area" on the screen. In other words, the machine cannot survive wherever it is located in some cases.

The world is as kind as it is cruel! There is a special item that helps the machine to survive any dangerous situation, even if it is exposed in a shower of laser beams, for some seconds. In addition, another straight line (called "a warning line") is drawn on the screen for a few seconds before a laser beam is emit along that line.

The only problem is that Nathan has a little slow reflexes. He often messes up the timing to use the special item. But he knows a good person who can write a program to make up his slow reflexes - it's you! So he asked you for help.

Your task is to write a program to make judgement whether he should use the item or not, for given warning lines and the radius of the machine.



Input

The input is a sequence of datasets. Each dataset corresponds to one situation with warning lines in the following format:

W H N R
x1,1 y1,1 x1,2 y1,2 t1
x2,1 y2,1 x2,2 y2,2 t2
...
xN,1 yN,1 xN,2 yN,2 tN


The first line of a dataset contains four integers W, H, N and R (2 < W ≤ 640, 2 < H ≤ 480, 0 ≤ N ≤ 100 and 0 < R < min{W, H}/2). The first two integers W and H indicate the width and height of the screen, respectively. The next integer N represents the number of laser beams.

The last integer R indicates the radius of the machine. It is guaranteed that the output would remain unchanged if the radius of the machine would become larger by 10-5 than R.

The following N lines describe the N warning lines. The (i+1)-th line of the dataset corresponds to the i-th warning line, which is represented as a straight line which passes through two given different coordinates (xi,1, yi,1 ) and (xi,2 , yi,2 ). The last integer ti indicates the thickness of the laser beam corresponding to the i-th warning line.

All given coordinates (x, y) on the screen are a pair of integers (0 ≤ x ≤ W, 0 ≤ y ≤ H). Note that, however, the machine is allowed to be located at non-integer coordinates during the play.

The input is terminated by a line with four zeros. This line should not be processed.

Output

For each case, print "Yes" in a line if there is a safe area, or print "No" otherwise.

Example

Input

100 100 1 1
50 0 50 100 50
640 480 1 1
0 0 640 480 100
0 0 0 0


Output

No
Yes

### Response

```cpp
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Point{
	Point(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}

	Point(){
		x = y = 0.0;
	}

	Point operator + (Point p){ return Point(x+p.x,y+p.y); }
	Point operator - (Point p){ return Point(x-p.x,y-p.y);}
	Point operator * (double a){ return Point(a*x,a*y); }
	Point operator / (double a){ return Point(x/a,y/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator<(const Point &p) const{
		return x != p.x? x < p.x: y < p.y;
	}

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
	}

	double x,y;
};
typedef Point Vector;

struct Circle{
	Point center;
	double r;
};

struct Line{
	Point p[2];
	Line(Point p1,Point p2){
		p[0] = p1;
		p[1] = p2;
		diff = 0;
	}
	Line(){
		diff = 0;
	}
	double diff;
};

int N;
double W,H,R;
vector<Line> WALL,LINE,CIRCLE_WALL,CIRCLE_LINE[105];

double norm(Vector a){
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a){
	return sqrt(norm(a));
}

double cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}

double dot(Vector a,Vector b){
    return a.x*b.x + a.y*b.y;
}


//交点を求める関数
Point calc_Cross_Point(double x1,double x2,double x3,double x4,double y1,double y2,double y3,double y4){
	Point ret;
	ret.x = ((x2-x1)*(y3*(x4-x3)+x3*(y3-y4))-(x4-x3)*(y1*(x2-x1)+x1*(y1-y2)))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
	if(x1 != x2){
		ret.y = ((y2-y1)*ret.x+y1*(x2-x1)+x1*(y1-y2))/(x2-x1);
	}else{
		ret.y = ((y4-y3)*ret.x+y3*(x4-x3)+x3*(y3-y4))/(x4-x3);
	}
	return ret;
}

//インタフェース関数
Point calc_Cross_Point(Point a,Point b,Point c,Point d){
	return calc_Cross_Point(a.x,b.x,c.x,d.x,a.y,b.y,c.y,d.y);
}

Point calc_Cross_Point(Line A,Line B){

	return calc_Cross_Point(A.p[0],A.p[1],B.p[0],B.p[1]);
}

Point calc_minus(Point a,Point b){
    Point ret;

    ret.x = a.x-b.x;
    ret.y = a.y-b.y;

    return ret;
}

double calc_len(Vector a){
    return sqrt(a.x*a.x+a.y*a.y);
}

//点と直線の距離(ただし、直線が無限長)
double calc_dist1(Line line,Point point){
    return abs(cross(line.p[1]-line.p[0],point-line.p[0]))/abs(line.p[1]-line.p[0]);
}

bool rangeCheck(Point point){

	return point.x >= R-EPS && point.x <= W-R+EPS && point.y >= R-EPS && point.y <= H-R+EPS;
}

bool is_OK(Point cross_point){

	if(!rangeCheck(cross_point))return false;

	//警告線と交差していないか調べる
	for(int c = 0; c < N; c++){

		double tmp_dist =  calc_dist1(LINE[c],cross_point);

		if(tmp_dist+EPS < R+LINE[c].diff){

			return false;
		}
	}

	//壁と交差していないか調べる
	for(int c = 0; c < 4; c++){

		double tmp_dist =  calc_dist1(WALL[c],cross_point);

		if(tmp_dist+EPS < R){

			return false;
		}
	}

	return true;
}


double calc_slope(Line A){

	if(fabs(A.p[0].x-A.p[1].x) < EPS){

		return DBL_MAX;

	}else if(fabs(A.p[0].y-A.p[1].y) < EPS){

		return 0;

	}else{

		return (A.p[0].y-A.p[1].y)/(A.p[0].x-A.p[1].x);
	}
}

bool is_Cross(Line A,Line B){

	return fabs(calc_slope(A)-calc_slope(B)) > EPS;
}

void func(){

	WALL.clear();
	LINE.clear();
	CIRCLE_WALL.clear();

	for(int i = 0; i < N; i++){

		CIRCLE_LINE[i].clear();
	}

	WALL.push_back(Line(Point(0,H),Point(0,0)));
	WALL.push_back(Line(Point(0,0),Point(W,0)));
	WALL.push_back(Line(Point(W,0),Point(W,H)));
	WALL.push_back(Line(Point(W,H),Point(0,H)));

	CIRCLE_WALL.push_back(Line(Point(R,H),Point(R,0)));
	CIRCLE_WALL.push_back(Line(Point(0,R),Point(W,R)));
	CIRCLE_WALL.push_back(Line(Point(W-R,0),Point(W-R,H)));
	CIRCLE_WALL.push_back(Line(Point(W,H-R),Point(0,H-R)));

	double diff;

	for(int i = 0; i < N; i++){

		Line tmp_line;

		scanf("%lf %lf %lf %lf %lf",&tmp_line.p[0].x,&tmp_line.p[0].y,&tmp_line.p[1].x,&tmp_line.p[1].y,&tmp_line.diff);
		LINE.push_back(tmp_line);

		//円を求めるため、平行移動した直線をあらかじめ求めておく

		Line top_line,under_line;

		if(fabs(tmp_line.p[0].x-tmp_line.p[1].x) < EPS){ //垂直な線分

			diff = tmp_line.diff+R;

			//p_top,p_underの設定
			top_line.p[0].x = tmp_line.p[0].x+diff;
			top_line.p[0].y = tmp_line.p[0].y;
			top_line.p[1].x = tmp_line.p[1].x+diff;
			top_line.p[1].y = tmp_line.p[1].y;

			CIRCLE_LINE[i].push_back(top_line);

			under_line.p[0].x = tmp_line.p[0].x-diff;
			under_line.p[0].y = tmp_line.p[0].y;
			under_line.p[1].x = tmp_line.p[1].x-diff;
			under_line.p[1].y = tmp_line.p[1].y;

			CIRCLE_LINE[i].push_back(under_line);

		}else{

			double slope = (tmp_line.p[1].y-tmp_line.p[0].y)/(tmp_line.p[1].x-tmp_line.p[0].x);

			diff = sqrt(slope*slope+1)*(R+tmp_line.diff);

			//p_top,p_underの設定
			top_line.p[0].x = tmp_line.p[0].x;
			top_line.p[0].y = tmp_line.p[0].y+diff;
			top_line.p[1].x = tmp_line.p[1].x;
			top_line.p[1].y = tmp_line.p[1].y+diff;

			CIRCLE_LINE[i].push_back(top_line);

			under_line.p[0].x = tmp_line.p[0].x;
			under_line.p[0].y = tmp_line.p[0].y-diff;
			under_line.p[1].x = tmp_line.p[1].x;
			under_line.p[1].y = tmp_line.p[1].y-diff;

			CIRCLE_LINE[i].push_back(under_line);
		}
	}

	//任意の2つの警告線について試す
	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			if(k == i)continue;

			for(int a = 0; a < 2; a++){
				for(int b = 0; b < 2; b++){

					if(!is_Cross(CIRCLE_LINE[i][a],CIRCLE_LINE[k][b]))continue;

					Point cross_point = calc_Cross_Point(CIRCLE_LINE[i][a],CIRCLE_LINE[k][b]);

					if(is_OK(cross_point)){

						printf("Yes\n");
						return;
					}
				}
			}
		}
	}


	//壁と壁
	for(int i = 0; i < 3; i++){
		for(int k = i+1; k < 4; k++){

			if(!is_Cross(CIRCLE_WALL[i],CIRCLE_WALL[k]))continue;

			Point cross_point = calc_Cross_Point(CIRCLE_WALL[i],CIRCLE_WALL[k]);

			if(is_OK(cross_point)){

				printf("Yes\n");
				return;
			}
		}
	}

	//任意の壁と、1つの警告線について試す
	for(int i = 0; i < 4; i++){
		for(int k = 0; k < N; k++){
			for(int a = 0; a < 2; a++){

				if(!is_Cross(CIRCLE_WALL[i],CIRCLE_LINE[k][a]))continue;

				Point cross_point = calc_Cross_Point(CIRCLE_WALL[i],CIRCLE_LINE[k][a]);

				if(is_OK(cross_point)){

					printf("Yes\n");
					return;
				}
			}
		}
	}

	printf("No\n");
}

int main(){

	int input_W,input_H,input_R;

	while(true){

		scanf("%d %d %d %d",&input_W,&input_H,&N,&input_R);
		if(input_W == 0 && input_H == 0 && N == 0 && input_R == 0)break;

		W = input_W,H = input_H,R = input_R;

		func();

	}

	return 0;
}


```