Algorithms and Data Structures

Sea Battle

notion image
You’re trying to develop the game “Sea Battle”. At the beginning of this game, each player places some battleships on a board at certain locations. Each battleship spans a straight line from to , where the connecting line between those coordinates is always perpendicular to the sides of the grid.
As a first step, you’d like to validate the grid to make sure, the users don’t put the battleships too close to each other or even intersect them. Each of the battleships needs to have at least a single cell of water distancing it from another ship. It’s okay to place the battleships next to the border without any water padding between the border and the ship.

Input

The first line of the input contains 3 integers n - the number of the battleships (1 ≤ n ≤ 20), w - the width of the battlefield (1 ≤ w ≤ 1000), and h - the height of the battlefield (1 ≤ h ≤ 1000).
The next n lines contain 4 integers - and (1 ≤ ≤ ≤ h) (1 ≤ ≤ ≤ w) coordinates of each battleship.

Output

The program should print Valid in case the grid is valid and Invalid otherwise.

Examples

Input
Output
2 10 10 1 1 1 5 8 1 8 10
Valid
2 10 10 1 1 1 5 2 3 2 10
Invalid
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue