Sea Battle
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
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 - 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