Curtain

Time limit8sMemory limit512 MB

Summary

Given an orthogonal polygon window and an axis-aligned rectangle curtain, find the area of the window that the curtain does not cover.

Level: Medium7 of 10
Topics: Geometry, Implementation, Brute force, Sorting
Solved: No attempts yet

Problem

Summer is coming soon. You decided to redecorate your room for the summer. This summer is expected to have very strong sunlight, so it will be a harsh season for you, who dislike glare. To adjust the brightness of the room, you decided to hang a curtain over the window.

The curtain is a rectangle, and it is hung so that its sides are perpendicular or parallel to the ground. The window in your room has a very unusual shape, given by an N-gon whose sides are each parallel or perpendicular to the ground. Because of this, it is hard to determine how much of the window remains uncovered by the curtain. To adjust the room's brightness, it is important to know how much of the window is covered when the curtain's position is chosen. So you decided to write a program that, given the window and the curtain's placement and shape, finds the area of the window not covered by the curtain.

As an example, consider the following window and curtain placement. In this case the area of the window not hidden by the curtain is 8. This example corresponds to the third sample input case.

Input

The input consists of multiple datasets. Each dataset is given in the following format.

N
x1 y1
:
:
xN yN
a1 b1
a2 b2
a3 b3
a4 b4

The first line gives the integer N, the number of vertices of the window (4 ≤ N ≤ 100). The following N lines give the integer xi, the x-coordinate, and the integer yi, the y-coordinate, of the distinct vertices of the window (-20,000 ≤ xi, yi ≤ 20,000, 1 ≤ i ≤ N). The positive direction of the y-axis is the direction obtained by rotating the positive direction of the x-axis 90 degrees counterclockwise. The following 4 lines give the integer aj, the x-coordinate, and the integer bj, the y-coordinate, of the distinct vertices of the curtain (-20,000 ≤ aj, bj ≤ 20,000, 1 ≤ j ≤ 4). For both the window and the curtain, the vertices are given in counterclockwise order. Also, the shapes representing the window and the curtain are each non-self-intersecting.

The end of the input is indicated by a line consisting of a single 0.

Output

For each dataset, output the area of the window not covered by the curtain on one line. Note that the area is always an integer.

Examples1

Example 1

Input

4
0 0
10 0
10 10
0 10
0 0
5 0
5 10
0 10
6
0 0
10 0
10 5
5 5
5 10
0 10
2 0
8 0
8 10
2 10
12
1 1
1 3
-1 3
-1 1
-3 1
-3 -1
-1 -1
-1 -3
1 -3
1 -1
3 -1
3 1
2 2
-2 2
-2 -2
2 -2
4
20000 20000
-20000 20000
-20000 -20000
20000 -20000
1000 1000
-1000 1000
-1000 -1000
1000 -1000
4
1000 1000
-1000 1000
-1000 -1000
1000 -1000
20000 20000
-20000 20000
-20000 -20000
20000 -20000
4
0 0
10 0
10 10
0 10
20 0
30 0
30 10
20 10
0

Expected output