На прямоугольный стол разложили N одинаковых листков бумаги со сторонами, параллельными краям стола. Необходимо прибить листки к столу гвоздями так, чтобы в каждый листик был вбит ровно один гвоздь, а каждым гвоздем прикреплялся к столу хотя бы один листок. Гвозди нельзя забивать в границы листков бумаги.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 20 секунд
Формат входных данных: В файле исходных данных записано количество листков N (1 Ј N Ј 100), длина листка L и его ширина W (1 Ј L, W Ј 1000). Далее следуют описания N листков, заданных координатами левого нижнего угла. Оси координат расположены по краям стола, начало координат находится в левом нижнем углу стола. Координаты точек - пары неотрицательных целых чисел, не превосходящих 1000. Все числа разделяются пробелами и/или символами перевода строки.
Формат выходных данных: Если вбить гвозди требуемым в условии способом невозможно, то необходимо поместить в выходной файл строчку "вбить гвозди невозможно". Если искомый способ существует, то программа должна вывести в выходной файл координаты гвоздей в произвольном порядке. Координаты гвоздей - вещественные числа. Числа в выходном файле должны разделяться пробелами и/или символами перевода строки.
Пример файлов входных и выходных данных:
| INPUT.TXT | OUTPUT.TXT |
| 3 | 66 |
| 10 10 | 13 7.5 |
| 0 0 5 5 12 3 |