5409: Hopping Rabbit

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:3 解决:0

题目描述

Little Rabbit loves hopping. He always hops around on the grassland. But dangers are lurking there --- the hunters have set traps. Once Little Rabbit falls into a trap, his life will be threatened. Therefore, Little Rabbit has to keep away from those traps.

Let's use two-dimensional Cartesian coordinate system to describe the grassland. We can regard Little Rabbit as a point, and regard traps as rectangles on the plane. The sides of the rectangles are parallel to the coordinate axes. We use two points to describe a rectangle --- the lower left point (x1,y1) and the upper right point (x2,y2) ( x1<x2 ,y1<y2 , x1,y1,x2,y2 are all integers).

Little Rabbit can hop in the direction of x -axis or y -axis. The length of each hop is d . Formally, if Little Rabbit locates at (x,y) , he can then hop to (x−d,y) , (x+d,y) , (x,y-d)(x,y−d) or (x,y+d)(x,y+d) .

Little Rabbit wants to find an initial position (x0+0.5,y0+0.5) ( x0 andy0 are integers) so that when he starts to hop from this point, no matter how he hops, he will never fall into a trap. Please help Little Rabbit to find such a point.

Please note that during a hop, Little Rabbit is in the air and won't fall into a trap. Little Rabbit will fall into a trap only if his landing point is in a trap.

输入

The first line contains two integers n and d(1≤n,d≤10e5) --- the number of traps and the length of each hop.Then in the next lines, each line contains four integers x1,y1,x2,y2
It's possible that the rectangles will intersect with each other.

输出

样例输入 复制

2 2
1 1 2 2
2 2 3 3

样例输出 复制

YES
3 2