eolymp
bolt
Try our new interface for solving problems
Məsələlər

Спички

Спички

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Спички детям не игрушка!

Инструктаж по пожарной безопасности

На игре "Форт Бойярд" команде лкшат вполне могут предложить следующую задачу: на столе лежат n спичек; требуется удалить ровно k из них так, чтобы в полученной конфигурации присутствовало ровно m квадратов.

Giriş verilənləri

В первой строке входного файла содержатся целые числа n, k и m (0 < k < n < 25, 0m50). В каждой из следующих n строк содержится описание очередной спички - четыре целых числа x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}, задающие координаты концов спички. Длина каждой спички равна 1. Никакие две спички не совпадают. Координаты не превышают 100 по абсолютной величине.

Çıxış verilənləri

Если получить ровно m квадратов нельзя, выведите в выходной файл единственное число -1.

В противном случае выведите k чисел - номера спичек, которые следует удалить. Спички нумеруются с единицы. Если решений несколько, выведите любое из них.

Nümunə

Giriş verilənləri #1
7 1 0
1 1 1 2
2 1 2 2
3 1 3 2
1 1 2 1
2 1 3 1
1 2 2 2
2 2 3 2
Çıxış verilənləri #1
2
Müəllif Ю.Петров, М.Дворкин