Морской бой

Вы разрабатываете игру “Морской бой”. В самом начале каждый игрок расставляет несколько кораблей на поле в определённых позициях. Каждый корабль располагается по прямой линии от до , при этом соединяющая их линия всегда перпендикулярна краям сетки.

На первом этапе вы хотите проверить игровое поле, чтобы убедиться, что пользователи не ставят корабли слишком близко друг к другу или не пересекают их. Между каждым кораблём и любым другим кораблём должна быть хотя бы одна клетка воды. Разрешается ставить корабли вплотную к границе, без дополнительного зазора между бортом корабля и краем поля.

Входные данные

Первая строка входных данных содержит 3 целых числа: n — количество кораблей (1 ≤ n ≤ 20), w — ширина поля боя (1 ≤ w ≤ 1000) и h — высота поля боя (1 ≤ h ≤ 1000).

В следующих n строках содержится по 4 целых числа — и (1 ≤ ≤ ≤ h, 1 ≤ ≤ ≤ w) — координаты каждого корабля.

Выходные данные

Программа должна вывести Valid, если расположение кораблей корректно, или Invalid — в противном случае.

Примеры