シーバトル
「シーバトル」というゲームを開発しようとしています。ゲームの開始時には、プレイヤー各自が盤面の特定の場所に複数の戦艦を配置します。戦艦はそれぞれ、 から までの一直線を占めており、その直線は常にグリッドの辺に対して垂直になります。
まずは、戦艦同士が近付きすぎたり重なったりしないかを検証するため、盤面をチェックしたいと考えています。各戦艦の周りには最低でも1マス分の水域が必要で、これによって船と船が隣接しないようにします。ただし、戦艦を盤面の端ぎりぎりに配置しても問題ありません。その場合は外枠との間に水域を設けなくて構いません。
Input
入力の最初の行には、3つの整数
n、w、h が与えられます。ここで n は戦艦の数 (1 ≤ n ≤ 20)、w は盤面の幅 (1 ≤ w ≤ 1000)、h は盤面の高さ (1 ≤ h ≤ 1000) を表します。続く
n 行には、それぞれ4つの整数 と が書かれています。これは各戦艦を表す座標で、(1 ≤ ≤ ≤ h) (1 ≤ ≤ ≤ w) の条件を満たします。Output
もし盤面の配置が有効であれば
Valid、そうでなければ Invalid を出力してください。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: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB