MFARM - Mineral Farm

no tags 

Alex has a huge farm land. Annual Farm Land Health Analysis Report by government revealed that some parts of his farms are rich in lot of valuable minerals. Now government want to conduct an air borne survey of his farm using huge laser devices attached to helicopters to calculate the exact quantity of minerals present in the farm. Each of these laser device has a rectangular base consisting of thousands of laser pores such that projection of device base on the ground will be analysed. These devices can be of different dimensions.

Now such survey will destroy the newly grown crops in the farm area that will be analysed. Government has sent Alex the map having the locations at which these devices will be used over his farms. Now Alex want to know how much crop would be left in the farm as compensation from the government for destroyed crop will take some time. Help Alex to identify the area of his farm land that will not be damaged by this survey. No device will inspect the surface outside the farm. To get more accurate mineral analysis same surface might be analysed by multiple devices. You can assume all devices will be parallel to the ground during the survey.

Input

First line of input contains 4 integers FX1, FY1, FX2, FY2 denoting the rectangular farm land owned by Alex.
Next line of input contains and integer N denoting number of laser devices that will be used.
Following N lines contains the location of these devices in the farm map. Every location is specified by 4 integers i.e. (x1,y1) and (x2,y2) which denotes the rectangular base of the device.

Output

Area of farm owned by Alex that will not be destroyed by the survey.

Constraints:

1 <= N <= 100000
-10^8 <= fx1, fx2, fy1, fy2, x1, x2, y1, y2 <= 10^8
min(fx1, fx2) <= x1, x2 <= max(fx1, fx2)
min(fy1, fy2) <= y1, y2 <= max(fy1, fy2)

Example

Input:
-10 -10 10 10
2
0 0 1 1
-2 3 4 6 Output: 381


Added by:XeRoN!X
Date:2015-03-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY