Table#9671
Famous chef Clémentine Deboeuf is buying new tables for her high-class restaurant. She has decided to go with the latest trend: a large model with numerous, wide yet delicate ornaments. However, she needs to ensure that these decorations do not interfere with the perfectly tuned ballet of dishes.
Ornaments reduce the amount of flat table surface where waiters can safely place dishes. Clémentine wants to make sure that all dishes can be put somewhere on the table in a sufficiently large safe area—that is, without overlapping any ornament. Given the dimensions and locations of all ornamental areas, Clémentine asks you to determine what impact these ornaments have on the locations available for dishes.
The table is a rectangle of width and length , given in millimeters. On top of it, ornaments are placed. Each is located at fixed table coordinates and shaped like a rectangle with sides parallel to the sides of the table. None of these areas overlap each other, though they can be adjacent.
In Clémentine's restaurant, all dishes are rectangular and are placed with sides parallel to the sides of the table, in a predetermined orientation. Waiters have millimetric precision: they will place dishes at integer millimeter coordinates, with sides parallel to those of the table. Dishes should not overlap any ornamental area (but they may touch its edges). Given a list of dishes described by their dimensions, your task is to determine, for each dish, the number of integer locations where it can be safely placed on the table.
Note: only one dish is served at a time on the table; this means that you do not need to worry about dishes overlapping each other. You can count the locations for each dish independently.
The first line contains integers , (1 \le X, Y \le 2000), (0 \le n \le 10^6), and (1 \le d \le 10^5).
Each of the next lines contains the coordinates of an ornament as four integers , x', , and y', where 0 \le x < x' \le X and 0 \le y < y' \le Y, describing an ornament spanning between the point and the point (x', y').
Each of the next lines contains the width and length of a dish as two integers, with 0 < x \le X and 0 < y \le Y.
Print lines, each containing the number of valid integer locations for the corresponding dish.
Example 1