Maps

Time limit1sMemory limit128 MB

Summary

Given up to a million arbitrarily rotated rectangles, find the number of edges of their common intersection polygon.

Level: Hard8 of 10
Topics: Geometry, Implementation, Math, Sorting
Solved: No attempts yet

Problem

Bajtazar owns a large collection of maps of Poland. Some are road maps, others are tourist maps, and so on. Every map has the shape of a rectangle, and a map may be rotated arbitrarily. Each map carries useful information about various places across the country.

Standing at a particular point, Bajtazar would like that point to appear on every one of his maps at once. He therefore wonders about the shape of the region that all the maps have in common. This common region is always a convex polygon, and your only task is to determine how many edges it has.

Task

Read the list of rectangles describing the area covered by each map.
Print the number of edges of the polygon formed by the common region of these rectangles.

Input

The first line contains one integer $n$ ( $1 \le n \le 10^6$ ), the number of rectangles.

Each of the next $n$ lines describes one rectangle with eight integers separated by single spaces: the coordinate pairs $(x_1, y_1)\ (x_2, y_2)\ (x_3, y_3)\ (x_4, y_4)$ of its four vertices listed in counter-clockwise order. Every coordinate satisfies $1 \le x, y \le 10^4$ .

You may assume that the area of the common region of all the rectangles is strictly greater than $0$ .

Output

Print a single integer: the number of edges of the polygon formed by the common region of the rectangles.

Hint

Examples5

Example 1

Input

3
3 3 11 3 11 9 3 9
5 2 11 5 8 11 2 8
9 1 10 1 10 11 9 11

Expected output

Example 2
Input
```
1
2 2 9 2 9 7 2 7
```
Expected output
```
4
```
Example 3
Input
```
2
2 2 8 2 8 8 2 8
5 1 9 5 5 9 1 5
```
Expected output
```
8
```

Example 4

Input

5
62 46 62 64 44 64 44 46
29 48 47 30 61 44 43 62
75 46 59 78 15 56 31 24
23 8 75 8 75 80 23 80
11 68 11 36 79 36 79 68

Expected output

Example 5

Input

5
68 68 30 68 30 30 68 30
74 52 48 78 24 54 50 28
47 15 83 33 51 97 15 79
57 90 17 50 51 16 91 56
60 37 60 57 32 57 32 37

Expected output