L. Постеры
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мебибайта
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Таня постоянно участвует в различных сборах по программированию. Каждый раз, приехав с очередных сборов, она вешает прямоугольный постер с этих сборов таким образом, что постеры не перекрываются друг с другом, а их стороны направлены по горизонтали и вертикали.

Сейчас Таня приехала с нескольких подряд поездок на сборы, и у неё набралось некоторое количество новых постеров. Для того, чтобы найти лучшее место для этих постеров, Таня рисует воображаемый прямоугольник со сторонами, параллельными сторонам существующих постеров, и смотрит, какова площадь той части прямоугольника, которая перекрывается с каким-либо постером.

Ваша задача — помочь Тане с подсчётами. Так как варианты перебираются один за другим, то ответ на каждый запрос необходимо выдавать до того, как поступил следующий.

Входные данные

В первой строке программа жюри передаёт программе участника четыре целых числа r, c, n, q (1 ≤ r, c ≤ 109, 0 ≤ n, q ≤ 50 000) — соответственно высоту и ширину стены, количество постеров и количество запросов.

В каждой из последующих n строк передаются по четыре целых числа x1, y1, x2, y2 (0 ≤ x1, x2 ≤ r, 0 ≤ y1, y2 ≤ c) — коолдинаты противоположных углов очередного постера. Гарантируется, что постеры не перекрываются.

После этого программа жюри выводит запросы. Каждый запрос состоит из четырёх целых чисел x1, y1, x2, y2 — координат противоположных углов очередного прямоугольника (0 ≤ x1, x2 ≤ r, 0 ≤ y1, y2 ≤ c).

Выходные данные

После каждого запроса выведите одно число — ответ на соответствующий запрос.

Пример
Входные данные
8 11 3 4
1 1 5 5
7 7 5 4
4 6 2 7
1 1 7 8
2 2 4 3
3 4 6 7
2 9 3 10
Выходные данные
24
2
6
0
Примечание

Для корректной работы программы после каждой операции вывода данных вам необходимо очищать буфер вывода, то есть делать следующие операции:

  • В языке Pascal: flush(output);
  • В С/С++: fflush(stdout) или cout.flush();
  • В Java: System.out.flush();
  • В Python: sys.stdout.flush() из библиотеки sys;
  • В C#: Console.Out.Flush();