Застройка территории
Мэр города решил, что для размещения участников олимпиады необходимо построить отель. Для этого он изучает план города и хочет найти на нём подходящий прямоугольный участок земли для строительства. На плане города обозначены N существующих зданий в виде прямоугольников. Для каждого здания указаны координаты противоположных вершин его прямоугольника.
Существует K проектов строительства отеля. Для каждого проекта указаны координаты соответствующего прямоугольного участка, который планируется выделить.
Напишите программу, которая из предложенных проектов выберет тот, который позволяет построить отель на свободном от существующих зданий месте и имеет максимальную площадь. При этом допускается, чтобы строительство велось непосредственно рядом с существующими зданиями.
Все стороны прямоугольников параллельны осям координат. Все координаты — целые числа от 0 до 10 000.
Входные данные
В первой строке записаны два целых числа — N и K (1 ≤ N, K ≤ 100). Во второй строке указаны координаты существующих зданий (по четыре числа на каждое здание). В третьей строке содержатся координаты возможных проектов строительства (также по четыре числа на каждый проект).
Выходные данные
Номер проекта, который будет выбран для строительства отеля. Если таких вариантов несколько, перечислите все проекты в порядке возрастания их номеров. Если ни один проект выбрать нельзя, выведите -1.