e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

ІІІ етап Всеукраїнської олімпіади з інформатик в Житомирській обл. 2019-2020

Забудова території

Міський голова вирішив, що для поселення учасників олімпіади потрібно побудувати готель. Для цього він взяв план міста і хоче знайти на ньому прямокутну земельну ділянку, де можна збудувати готель. На плані міста у вигляді прямокутників нанесено N наявних будинків. Для кожного будинку задані координати протилежних вершин відповідного прямокутника.

Існують K проектів будівництва готелю. Для кожного проекту задані координати відповідної прямокутної ділянки, яку планується виділити.

Напишіть програму, яка з-поміж запропонованих проектів обирає той, який дозволяє збудувати готель у вільному від наявних будинків місці та дозволяє обрати проект з максимальною площею забудови. При цьому допускається, щоб будівництво виконувалося безпосередньо біля наявних будівель.

Сторони усіх прямокутників паралельні осям координат. Всі координати представляють собою цілі числа від 0 до 10 000.

Вхідні дані.

У першому рядку записані два цілих числа – N і K (**1 ≤ N, K ≤ 100**). У другому рядку задаються координати наявних будинків (по чотири числа на кожний будинок). Третій рядок містить координати можливих проектів будівництва (також по чотири числа на кожний проект).

Вихідні дані. Номер проекту, який буде вибрано для будівництва готелю. Якщо таких варіантів декілька, перерахуйте усі проекти у порядку зростання їх номерів. Якщо жодного проекту обрати не можна, виведіть -1.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 2
1 1 15 3 1 5 6 7 10 5 15 7
6 5 10 7 2 2 14 4
Output example #1
1
Source XXXIV обласна олімпіада з інформатики