Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type
2017 Fall Waterloo Local ACM Contest, Problem E

Vera has NN rectangles. The ii-th rectangle has corners (a_i, b_i)(a_i, b_i) and (c_i, d_i)(c_i, d_i). Let UU be the union of the NN rectangles. The intersection of UU and the line y = s - xy = s - x is composed of disjoint line segments (maybe degenerate ones). Let f(s)f(s) be the sum of the lengths of these line segments or be zero if the intersection is empty.

Given integers LL and RR, let S = \sum_{s=L}^R f(s)S = \sum_{s=L}^R f(s). It can be seen that S = V \sqrt 2S = V \sqrt 2 for some integer VV. Compute the value of VV.

Input

Line 11 contains integers N, L, RN, L, R (1 \le N \le 10^3, -2 \times 10^8 \le L < R \le 2 \times 10^8)(1 \le N \le 10^3, -2 \times 10^8 \le L < R \le 2 \times 10^8).

NN lines follow. The ii-th line contains integers a_i, b_i, c_i, d_ia_i, b_i, c_i, d_i (-10^8 \le a_i < c_i \le 10^8, -10^8 \le b_i < d_i \le 10^8)(-10^8 \le a_i < c_i \le 10^8, -10^8 \le b_i < d_i \le 10^8).

Output

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

Sample Input

3 -1 3
-2 -1 0 2
-1 0 1 1
1 -2 2 -1

Sample Output

7

Note

The below figure illustrates the first example when s = 0s = 0. f(0)f(0) is the sum of the lengths of the two thick blue line segments. Note that S = 7 \sqrt{2} \approx 9.899S = 7 \sqrt{2} \approx 9.899.


Comments

There are no comments at the moment.