408872: GYM103366 L It Rains Again

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. It Rains Againtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Suppose that in a Cartesian coordinate system on an infinite plane, the x-axis represents the ground and there are n rainscreens (We don't consider their thickness.) in the sky.

Every rainscreen can be described as a segment which starts from the $$$(x_1,y_1)$$$ and ends at $$$(x_2,y_2)$$$. Now if it starts to rain from the infinite high sky, I want you to tell me how many units of the x-axis will not get rained on.

To simplify the problem,the rain can only move vertically whenever it falls.

Note that two rainscreens can overlap and intersect with each other, and there is no rainscreen which is placed vertically.

Input

The first line contains one positive integer $$$n (1 \leq n \leq 100000)$$$.

Each of the next n lines contains four positive integers $$$x_1, y_1, x_2, y_2 (1 \leq x_1 < x_2 \leq 100000, 1 \leq y_1,y_2 \leq 100000)$$$, representing a rainscreen which starts from the $$$(x_1, y_1)$$$ and ends at $$$(x_2, y_2)$$$.

Output

The only one integer - the number of units of the x-axis which will not get rained on.

ExampleInput
5
1 2 2 1
1 1 2 2
3 3 4 3
5 1 6 3
6 3 7 2
Output
4
Note

Consider the example, we can draw a picture like below:

It's easy to calculate the answer is 4.

加入题单

上一题 下一题 算法标签: