Это интерактивная задача.
Таня постоянно участвует в различных сборах по программированию. Каждый раз, приехав с очередных сборов, она вешает прямоугольный постер с этих сборов таким образом, что постеры не перекрываются друг с другом, а их стороны направлены по горизонтали и вертикали.
Сейчас Таня приехала с нескольких подряд поездок на сборы, и у неё набралось некоторое количество новых постеров. Для того, чтобы найти лучшее место для этих постеров, Таня рисует воображаемый прямоугольник со сторонами, параллельными сторонам существующих постеров, и смотрит, какова площадь той части прямоугольника, которая перекрывается с каким-либо постером.
Ваша задача — помочь Тане с подсчётами. Так как варианты перебираются один за другим, то ответ на каждый запрос необходимо выдавать до того, как поступил следующий.
В первой строке программа жюри передаёт программе участника четыре целых числа 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
Для корректной работы программы после каждой операции вывода данных вам необходимо очищать буфер вывода, то есть делать следующие операции:
| Name |
|---|


