404459: GYM101510 E English

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

Description

E. Englishtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Vera has N rectangles. The i-th rectangle has corners (ai, bi) and (ci, di). Let U be the union of the N rectangles. The intersection of U and the line y = s - x is composed of disjoint line segments (maybe degenerate ones). Let f(s) be the sum of the lengths of these line segments or be zero if the intersection is empty.

Given integers L and R, let . It can be seen that for some integer V. Compute the value of V.

Input

Line 1 contains integers N, L, R (1 ≤ N ≤ 103,  - 2 × 108 ≤ L < R ≤ 2 × 108).

N lines follow. The i-th line contains integers ai, bi, ci, di ( - 108 ≤ ai < ci ≤ 108,  - 108 ≤ bi < di ≤ 108).

Output

Print one line with one integer, the value of V.

ExampleInput
3 -1 3
-2 -1 0 2
-1 0 1 1
1 -2 2 -1
Output
7
Note

The below figure illustrates the first example when s = 0. f(0) is the sum of the lengths of the two thick blue line segments. Note that .

加入题单

上一题 下一题 算法标签: