P15058 [UOI 2023 II Stage] Rectangles are everywhere

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$ 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.