On an field of size rows by columns, Matthew is running a construction operation.
He selects rectangular plots of land as sites to build barriers. Each plot of land is bounded by the rectangle with corners and .
After selecting the sites, he wants to know whether its possible to traverse from to while avoiding barriers. Movement is done only in cardinal directions (up, down, left, right).
Input Specifications
The first line will contain two space-separated integers, and , representing the number of rows and columns on the field.
The second line will contain , representing the number of marked plots of land.
The next lines each contain four space-separated integers, , , , and , representing the plots of land. These coordinates are guaranteed to be within the boundaries of the field.
Output Specifications
Output YES
if the traversal is possible or NO
otherwise.
Sample Input 1
5 6
2
3 1 4 3
1 3 3 6
Sample Output 1
NO
Sample Explanation 1
The following image represents the grid, where black cells are marked cells.
Sample Input 2
5 6
2
3 1 4 3
3 5 4 6
Sample Output 2
YES
Sample Explanation 2
The following image represents the grid, where black cells are marked cells.
Comments
Instead of the next Q lines, it should be the next T lines, right?