题目描述

Andriyko drank a lot of compote and now he's very afraid of rectangles. Andriyko's room can be mathematically represented as a rectangle with height $n$ and width $m$. In this room, there are $k$ rectangles, each of which is completely inside the room and does not touch the points $(0,0)$ and $(n,m)$ (where $(0,0)$ is the top-left and $(n,m)$ is the bottom-right point).

Andriyko wants to go from the corner $(0,0)$ to $(n,m)$ without ever touching any of the $k$ rectangles (not even touching them). If he is at coordinate $(x,y)$, then he can move to any of the following coordinates with one step: $(x-0.5,y)$, $(x+0.5,y)$, $(x,y-0.5)$, $(x,y+0.5)$, but only if the next coordinate does not go beyond the boundaries of the rectangle.

Determine if he can reach from one corner to the other.

输入格式

The first line contains three integers $n$, $m$, $k$ $(1 \le n,m \le 10^6, 1 \le k \le 5\,000)$.

Each of the next $k$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$ $(0 \le x_1 \le x_2 \le n; 0 \le y_1 \le y_2 \le m)$ --- the coordinates of the top-left and bottom-right corners of rectangle $i$.

It is guaranteed that no rectangle touches the points $(0,0)$ and $(n,m)$.

输出格式

Print $\tt{YES}$ if Andriyko can travel between the ends of the room, and $\tt{NO}$ otherwise.

3 4 3
0 2 1 4
1 2 3 3
2 1 3 3

NO

3 4 3
0 2 1 4
1 0 2 1
2 1 3 3

YES

提示

• ($3$ points): $k = 1$
• ($4$ points): $k = 2$
• ($5$ points): $k = 3$
• ($17$ points): $1 \le k \le 50$
• ($26$ points): $1 \le k \le 1000$
• ($20$ points): $1 \le n,m \le 5000$
• ($25$ points): no additional constraints.