Nezumi's Treasure

Time limit2sMemory limit512 MB

Summary

Count the points where a mouse that turns left at each rectangle obstacle could hide his fish at the first turn after entering an infinite loop.

Level: Hard8 of 10
Topics: Geometry, Simulation, Graph, Sorting
Solved: No attempts yet

Problem

A mouse and a cat lived in a field. The mouse stole a dried fish that the cat loved. The theft was discovered soon after. The mouse started running with the dried fish while the cat chased him.

There were several rectangular obstacles in the field. The mouse always went straight ahead as long as he could, but he could not jump over or pass through these obstacles. When he was blocked by an obstacle, he turned left toward a direction he could move forward in, and then started running in that direction again. Note that at a corner, he might be able to keep going without changing direction.

He found that he kept passing the same point again and again while being chased. He then decided to hide the dried fish at the first point where he was blocked by an obstacle for the second time after that. In other words, he decided to hide it at the first turn after he entered an infinite loop. He thought he could come back there after the chase ended.

For example, in the figure below, he first went along the blue line and turned left at point B. Then he went counter-clockwise along the red lines and entered an infinite loop. In this case, he hid the dried fish at point A, not point B, because when he reached point B on line C the second time, he just passed through and did not turn left.

Example of a dried fish hiding point

In the end, the cat went away, but he remembered neither the point where he had planned to hide the fish nor the point where he actually hid it. He had lost his dried fish.

You are a friend of the mouse and a talented programmer. Write a program that counts the number of points where the mouse could have hidden the dried fish, given the obstacles. The mouse is treated as a point.

Input

The first line contains one integer $N$ ( $4 \le N \le 40000$ ), the number of obstacles. The next $N$ lines each describe one obstacle with four integers $X_{i,1}$ , $Y_{i,1}$ , $X_{i,2}$ , and $Y_{i,2}$ ( $-100000000 \le X_{i,1}, Y_{i,1}, X_{i,2}, Y_{i,2} \le 100000000$ ). $(X_{i,1}, Y_{i,1})$ are the coordinates of the lower-left corner of the obstacle, and $(X_{i,2}, Y_{i,2})$ are the coordinates of its upper-right corner. The X-axis points right and the Y-axis points up. No two obstacles overlap.

Output

Print the number of points where the mouse could have hidden the dried fish. You can assume this number is positive.

Examples2

Example 1
Input
```
4
0 0 2 1
3 0 4 2
0 2 1 4
2 3 4 4
```
Expected output
```
4
```

Example 2

Input

Expected output