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$.