수족관 1

수족관을 정면에서 본 단면이 아래 그림 1과 같다. 수족관에는 물이 가득 차 있다. 수족관 바닥(수평선분)에 구멍을 하나 뚫으면, 그 구멍을 통해 물이 빠져나간다.

그림 1. 수족관과 구멍.

수족관의 경계는 꼭짓점들로 나타낸다. 각 꼭짓점의 위치는 (세로줄 번호, 가로줄 번호)로 표현한다. 세로줄 번호는 왼쪽에서 오른쪽으로 $0$부터 $1$씩 커지고, 가로줄 번호는 위에서 아래로 $0$부터 $1$씩 커진다. 이웃한 두 세로줄 사이의 거리와 이웃한 두 가로줄 사이의 거리는 모두 $1$이다. 따라서 왼쪽 위 꼭짓점의 위치는 $(0, 0)$이며, 이 꼭짓점에서 시작해 시계 반대 방향으로 경계를 따라가면 만나는 꼭짓점은 차례로 $(0, 5)$, $(8, 5)$, $(8, 0)$이다.

바닥의 어떤 수평선분에 구멍이 있으면, 그 수평선분보다 위쪽에 있으면서 중력에 따라 그 구멍으로 흘러갈 수 있는 물은 모두 구멍을 통해 밖으로 빠진다. 그래서 그림 1의 물은 바닥 구멍을 통해 남김없이 모두 빠진다.

수족관에 담긴 물의 양은 물이 차지하는 넓이와 같고, 단위는 L(리터)이다. 따라서 그림 1에서 가득 찬 물의 양은 넓이와 같은 40 L이다.

그림 2처럼 바닥 모양이 더 복잡할 수도 있다. 바닥은 수평선분과 수직선분이 번갈아 나타나는 형태이며, 수족관을 바로 위에서 수직으로 내려다보면 모든 수평선분이 빠짐없이 보인다. 즉 바닥에는 위에서 가려지는 부분이 없다.

그림 2. 가득 찬 물의 양은 26 L, 구멍은 2개.

구멍은 항상 수평선분 위에만 있으며, 그 수평선분의 한가운데에 위치한다. 하나의 수평선분에는 구멍이 최대 하나만 있을 수 있다. 그림 2에는 구멍이 2개 있다. 이 구멍들로 물을 빼면, 그림 3처럼 빠져나가지 못한 물이 7 L 남는다.

그림 3. 마지막에 남은 물의 양은 7 L.

물이 가득 찬 수족관의 바닥 모양과 구멍이 뚫린 수평선분들이 주어질 때, 구멍으로 물이 빠져나간 뒤 수족관에 남아 있는 물의 양이 몇 리터인지 구하는 프로그램을 작성하시오.

첫째 줄에 수족관 경계에 있는 꼭짓점의 개수 $N$이 주어진다. ($1 \le N \le 5{,}000$, $N$은 짝수)

수족관의 경계는 항상 꼭짓점 $(0, 0)$에서 시작해 꼭짓점 $(A, 0)$에서 끝난다. 즉 시작 꼭짓점과 마지막 꼭짓점의 가로줄 번호는 모두 $0$이다. 경계를 이루는 변은 꼭짓점 $(0, 0)$에서 출발해 먼저 수직선분으로 시작하고, 이후 수평선분과 수직선분이 번갈아 나오다가 수직선분으로 끝난다. 따라서 수직선분이 수평선분보다 항상 하나 더 많다.

둘째 줄부터 $N$개의 줄에 걸쳐, 경계에 있는 꼭짓점 $N$개의 세로줄 번호와 가로줄 번호가 한 줄에 하나씩 공백으로 구분되어 주어진다. 꼭짓점은 시작 꼭짓점 $(0, 0)$부터 시계 반대 방향 순서로 주어진다. 세로줄 번호와 가로줄 번호는 모두 $0$ 이상 $40{,}000$ 이하의 정수이다.

그다음 줄에는 구멍의 개수 $K$가 주어진다. ($1 \le K \le N/2$)

이어지는 $K$개의 줄에는 각 구멍이 있는 수평선분의 두 끝점을 나타내는 네 정수 $a$, $b$, $c$, $b$가 공백으로 구분되어 주어진다. 이는 구멍이 꼭짓점 $(a, b)$와 꼭짓점 $(c, b)$를 잇는 수평선분 위에 있다는 뜻이다. 항상 $a < c$이다.

구멍으로 물이 빠져나간 뒤 수족관에 남아 있는 물의 양을 $0$ 이상의 정수로 한 줄에 출력한다.