Стол
Известный шеф-повар Клементина Дебоф покупает новые столы для своего ресторана высокого класса. Она решила пойти по последнему тренду - большой модели с многочисленными широкими, но в то же время изысканными орнаментами. Тем не менее, она должна быть уверена, что эти декорации не помешают идеально настроенному балу блюд.
Украшения уменьшают количество плоской поверхности стола, где официанты могут безопасно ставить посуду. Клементина хочет сделать так, чтобы все блюда можно было положить на стол где-нибудь на достаточно большом безопасном месте, то есть без наложения каких-либо украшений. Зная размеры и расположение всех декоративных областей, Клементина просит Вас рассказать ей, как эти украшения влияют на места, доступные для посуды.
Стол представляет собой прямоугольник шириной X и длиной Y миллиметров. Поверх него размещены n орнаментов. Каждый из них расположен в фиксированных координатах стола и имеет форму прямоугольника, стороны которого параллельны сторонам стола. Конечно, ни одна из этих областей не перекрывает друг друга, но они могут касаться друг друга.
В ресторане Clémentine все d блюд имеют прямоугольную форму и располагаются так, чтобы их стороны были параллельны сторонам стола в заранее определенной ориентации. Официанты имеют миллиметровую точность: они будут размещать блюда в целочисленных миллиметровых координатах так, чтобы их стороны были параллельны сторонам стола. Блюда не должны перекрывать любую декоративную область (но они могут касаться ее краев). Учитывая список блюд, описываемых их размерами, ваша задача состоит в том, чтобы указать для каждого из них количество (целых) мест, где его можно безопасно разместить на столе. Примечание: на стол подается только одно блюдо; это означает, что Вам не нужно беспокоиться о том, что блюда могут перекрываться, вы можете рассчитывать места для каждого блюда независимо от других.
Входные данные
Первая строка содержит целые числа X, Y (1 ≤ X, Y ≤ 2000), n (0 ≤ n ≤ 10^6) и d (1 ≤ d ≤ 10^5). Каждая из следующих n строк содержит координаты орнамента - четыре целых числа x, x', y и y', где 0 ≤ x < x' ≤ X и 0 ≤ y < y' ≤ Y, описывающие орнамент между точками (x, y) и (x`, y'). Следующие d строк содержат ширину x и длину y блюд - два целых числа, 0 < x ≤ X и 0 < y ≤ Y.
Выходные данные
Выведите d строк, содержащих количество возможных расположений для каждого блюда.
