Rating changes for the last round are temporarily rolled back. They will be returned soon.
×

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Visible Black Areas

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPetya has a polygon consisting of $$$n$$$ vertices. All sides of the Petya's polygon are parallel to the coordinate axes, and each two adjacent sides of the Petya's polygon are perpendicular. It is guaranteed that the polygon is simple, that is, it doesn't have self-intersections and self-touches. All internal area of the polygon (borders are not included) was painted in black color by Petya.

Also, Petya has a rectangular window, defined by its coordinates, through which he looks at the polygon. A rectangular window can not be moved. The sides of the rectangular window are parallel to the coordinate axes.

Determine the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

Input

The first line contain four integers $$$x_1, y_1, x_2, y_2$$$ ($$$x_1 < x_2$$$, $$$y_2 < y_1$$$) — the coordinates of top-left and bottom-right corners of the rectangular window.

The second line contains a single integer $$$n$$$ ($$$4 \le n \le 15\,000$$$) — the number of vertices in Petya's polygon.

Each of the following $$$n$$$ lines contains two integers — the coordinates of vertices of the Petya's polygon in counterclockwise order. Guaranteed, that the given polygon satisfies the conditions described in the statement.

All coordinates of the rectangular window and all coordinates of the vertices of the polygon are non-negative and do not exceed $$$15\,000$$$.

Output

Print the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

Example

Input

5 7 16 3

16

0 0

18 0

18 6

16 6

16 1

10 1

10 4

7 4

7 2

2 2

2 6

12 6

12 12

10 12

10 8

0 8

Output

2

Note

The example corresponds to the picture above.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2021 16:23:03 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|