Aquarium 1

The cross-section of an aquarium seen from the front looks like Figure 1 below. The aquarium is completely full of water. If you drill a single hole in the bottom of the aquarium (a horizontal segment), water drains out through that hole.

Figure 1. The aquarium and a hole.

The boundary of the aquarium is described by its vertices. Each vertex position is given as (column number, row number). Column numbers increase by $1$ from left to right starting at $0$, and row numbers increase by $1$ from top to bottom starting at $0$. The distance between two neighboring columns and the distance between two neighboring rows are both $1$. Hence the top-left vertex is at $(0, 0)$, and starting from it and following the boundary counterclockwise, the vertices you meet are $(0, 5)$, $(8, 5)$, $(8, 0)$ in order.

If a horizontal segment of the bottom has a hole, then all water that lies above that segment and can flow to the hole under gravity drains out through it. Therefore all of the water in Figure 1 drains out completely through the bottom hole.

The amount of water held by the aquarium equals the area the water occupies, measured in L (liters). So in Figure 1 the full amount of water is 40 L, equal to the occupied area.

As in Figure 2, the bottom can be more complicated. The bottom consists of horizontal and vertical segments that alternate, and when you look straight down on the aquarium from directly above, every horizontal segment is visible; that is, no part of the bottom is hidden from above.

Figure 2. The full amount of water is 26 L, and there are 2 holes.

A hole always lies on a horizontal segment, exactly at its midpoint. Each horizontal segment can contain at most one hole. Figure 2 has 2 holes. Draining water through them leaves 7 L of water that cannot escape, as shown in Figure 3.

Figure 3. The final amount of water left is 7 L.

Given the shape of the bottom of a full aquarium and the horizontal segments that have holes, write a program that computes how many liters of water remain in the aquarium after the water has drained out through the holes.

The first line contains the number of vertices on the aquarium boundary, $N$ ($1 \le N \le 5{,}000$, and $N$ is even).

The boundary always starts at vertex $(0, 0)$ and ends at vertex $(A, 0)$; that is, the row number of both the first and the last vertex is $0$. Starting from $(0, 0)$, the boundary begins with a vertical segment, then horizontal and vertical segments alternate, and it ends with a vertical segment. Thus there is always exactly one more vertical segment than horizontal segments.

Each of the next $N$ lines contains the column number and the row number of one boundary vertex, separated by a space. The vertices are given in counterclockwise order starting from $(0, 0)$. All column and row numbers are integers between $0$ and $40{,}000$ inclusive.

The next line contains the number of holes $K$ ($1 \le K \le N/2$).

Each of the following $K$ lines contains four integers $a$, $b$, $c$, $b$ separated by spaces, describing the two endpoints of the horizontal segment on which a hole lies. This means the hole is on the segment connecting vertex $(a, b)$ and vertex $(c, b)$. It is always the case that $a < c$.

Print, on a single line, the amount of water remaining in the aquarium after it has drained through the holes, as an integer greater than or equal to $0$.