Counting Subrectangles Covering All Points

Given an axis-aligned rectangle A with vertices at integer coordinates and edges parallel to the coordinate axes, and n integer points p₁, p₂, ..., p_n that lie inside or on the boundary of A, count the number of subrectangles of A that satisfy the following conditions:

• The vertices of the subrectangle are integer points.
• Each of its four sides is parallel to one of the coordinate axes.
• The subrectangle covers all the given points (points on the boundary are allowed).

Note that the length or width of the rectangle may be 0 (degenerate rectangles are allowed).

Hint: Let the rectangle A be defined by two opposite corners, where x_min and y_min are the minimum x and y coordinates and x_max and y_max are the maximum x and y coordinates respectively. Define:

$$p_{min\_x}=\min_{1\leq i \leq n}\{p_{i,x}\}, \quad p_{max\_x}=\max_{1\leq i \leq n}\{p_{i,x}\},$$ $$p_{min\_y}=\min_{1\leq i \leq n}\{p_{i,y}\}, \quad p_{max\_y}=\max_{1\leq i \leq n}\{p_{i,y}\}.$$

Then any subrectangle defined by its x-coordinates \(X_1\) and \(X_2\) (with \(x_{min} \leq X_1 \leq X_2 \leq x_{max}\)) and y-coordinates \(Y_1\) and \(Y_2\) (with \(y_{min} \leq Y_1 \leq Y_2 \leq y_{max}\)) covers all the points if and only if:

$$X_1 \leq p_{min\_x} \quad \text{and} \quad X_2 \geq p_{max\_x},$$ $$Y_1 \leq p_{min\_y} \quad \text{and} \quad Y_2 \geq p_{max\_y}.$$

The total number of valid subrectangles is:

$$\text{answer} = (p_{min\_x} - x_{min} + 1)\times (x_{max} - p_{max\_x} + 1)\times (p_{min\_y} - y_{min} + 1)\times (y_{max} - p_{max\_y} + 1).$$

inputFormat

The input consists of multiple lines:

1. The first line contains four integers: x1 y1 x2 y2, representing two opposite corners of rectangle A. (Note: you should treat the smaller of x1 and x2 as x_min and similarly for y.)
2. The second line contains an integer n, the number of points.
3. Each of the next n lines contains two integers representing the coordinates of a point that lies inside or on the boundary of A.

outputFormat

Output a single integer, the number of subrectangles of A that cover all the given points.

sample

0 0 5 5
1
2 3

144