2017 Fall Waterloo Local ACM Contest, Problem E

Vera has ~N~ rectangles. The ~i~-th rectangle has corners ~(a_i, b_i)~ and ~(c_i, d_i)~. 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 ~S = \sum_{s=L}^R f(s)~. It can be seen that ~S = V \sqrt 2~ for some integer ~V~. Compute the value of ~V~.

Input

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

~N~ lines follow. The ~i~-th line contains integers ~a_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)~.

Output

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

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 = 0~. ~f(0)~ is the sum of the lengths of the two thick blue line segments. Note that ~S = 7 \sqrt{2} \approx 9.899~.