## IPSC 2004

## Problem H – Hard Question – P=NP?

Students of computer science in Bratislava enjoy hiking and
camping during their long summer breaks. They love walking silently
in the groves, visiting sparkling waterfalls, exploring dark caves,
climbing steep hills, or just sleeping in a tent. Some of them already
visited all the national parks in Slovakia and nearby countries.

With no more new national parks to visit, frustrated students
decided to set up a new national park (NP) by themselves. After long
arguing, they finally agreed on the boundary of the NP. Now
they want to purchase all the land needed for NP from present
owners. Their funds are limited (after all, they are only students),
therefore they do not want to buy any land outside the NP.

### Task specification

The NP can be described as a polygon
with **N** vertices. There is a set P of **M** rectangular plots
of land available for sale by their owners. The rectangles are
mutually disjoint and axis-parallel. Your task is to decide whether
it is possible to purchase subset of plots P exactly covering the
proposed NP.

### Input specification

Input file consists of several test
cases separated by a blank line. Each test case starts with two
integers **N** and **M**. Next **N** lines contain the
coordinates of the vertices of the NP. Each of the following **M**
lines describes one plot. For each plot, the coordinates of two
opposite corners of the rectangle are given. The values **N=0**,
**M=0** end the input and should not be processed.

### Output specification

For each test case output either
'YES' or 'NO' depending on whether it is possible to set up the
NP using P or not.

### Example

**Input:**
4 3
0 0
0 2
2 2
2 0
1 0 0 2
1 0 2 2
3 1
0 0
2 2
2 0
0 0 1 1
0 0

**Output:**
YES
NO