Lucky Number

You are given an integer $n$ and $n$ pairs of integer intervals. For each $1 \le i \le n$, you are given two intervals: $a_i \in [l_{i,1}, r_{i,1}]$ and $b_i \in [l_{i,2}, r_{i,2}]$. Initially, an empty multiset $S$ is maintained. The process lasts for $n$ rounds. In the $i$-th round, you choose an integer $a_i$ from the interval $[l_{i,1}, r_{i,1}]$, and add $a_i$ copies of some integer $b_i$ (which you choose from the interval $[l_{i,2}, r_{i,2}]$) into $S$.

Let ( m = \sum_{i=1}^{n} a_i ); hence, after all $n$ rounds, the multiset $S$ contains $m$ numbers. The lucky number is defined as the median of $S$, i.e. the ( \left\lfloor \frac{m+1}{2} \right\rfloor )-th smallest element in $S$.

However, you do not know the exact values of the $n$ pairs. Instead, for each $1 \le i \le n$, you know only the ranges of possible values: $a_i \in [l_{i,1}, r_{i,1}]$ and $b_i \in [l_{i,2}, r_{i,2}]$. Your task is to determine how many distinct integers may possibly be the lucky number considering all valid choices of $a_i$ and $b_i$ from their respective intervals.

Note: An integer $x$ can be the lucky number if and only if there exists some valid assignment of all $a_i$ and $b_i$ such that when all rounds are performed the median of $S$ is exactly $x$. Formally, if we denote by $L$ the number of elements that are guaranteed to be less than $x$, and by $E$ the number of elements from rounds where $x$ can be chosen (i.e. $x \in [l_{i,2}, r_{i,2}]$), then by appropriate choices, $x$ can be the median if there exists an integer $t$ with [ L < t \le L+E \quad \text{and} \quad t = \left\lfloor \frac{m+1}{2} \right\rfloor ] for some total $m$ in the achievable range. In the input, one may assume that all intervals are such that every integer in the union of all $b_i$ intervals is a candidate.

All formulas are given in (\LaTeX) format.

inputFormat

The first line contains a single integer n representing the number of rounds.

Each of the following n lines contains four integers: li,1 ri,1 li,2 ri,2, describing the ranges for ai and bi respectively.

You may assume that all provided intervals are valid and that the union of all intervals for bi is small enough to iterate over.

outputFormat

Output a single integer denoting the number of distinct integers that may possibly be the lucky number.

sample

2
1 3 1 2
2 4 2 3

3