Rectangles Everywhere#11374
Andriiko drank too much compote, and now he is very afraid of rectangles. Andriiko's room can be mathematically represented as a rectangle with height and width . In this room, there are rectangles, each of which lies completely within the room and does not touch the points and , where point is the top-left corner and is the bottom-right corner.
Andriiko wants to get from corner to corner without ever being inside any of the rectangles (not even touching them). If he is at coordinate , then in one step he can move to any of the following coordinates: (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 outside the boundaries of the room.
Determine whether he can get from one corner to the other.
The first line contains three integers , , (1 \le n,m \le 10^6, 1 \le k \le 5\,000).
Each of the next 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 .
It is guaranteed that no rectangle touches the points and .
Print «YES» if Andriiko can travel between the corners of the room, and «NO» otherwise.
Example 1
Example 2
( points): k = 1
( points): k = 2
( points): k = 3
( points): 1 \le k \le 50
( points): 1 \le k \le 1000
( points): 1 \le n,m \le 5000
( points): No additional constraints