Development of the territory
The mayor has decided that a hotel needs to be constructed to accommodate the participants of the Olympics. To achieve this, he has reviewed the city plan and aims to identify a rectangular plot of land suitable for the hotel.
The city plan includes N existing buildings, each represented as a rectangle. For each building, the coordinates of two opposite vertices of the rectangle are provided.
There are K proposed hotel construction projects. For each project, the coordinates of the rectangular plot intended for the hotel are given.
Your task is to write a program that selects the project which allows for the hotel to be built on a plot that is free from existing buildings, while also maximizing the construction area. It is acceptable for the hotel to be built adjacent to existing buildings.
All rectangle sides are aligned with the coordinate axes. All coordinates are integers ranging from 0 to 10,000.
Input data.
The first line contains two integers, N and K (1 ≤ N, K ≤ 100). The second line provides the coordinates of the existing buildings (four numbers for each building). The third line contains the coordinates for the potential construction projects (also four numbers for each project).
Output data.
Output the number of the project selected for hotel construction. If multiple projects meet the criteria, list all project numbers in ascending order. If no suitable project can be selected, output -1.