Little Sasha has two girlfriends whom he wants to please with gifts for the Eighth of March. To do this, he went to the largest shopping center in the city.

There are $n$ departments in the shopping center, each containing exactly two stores. For convenience, we number the departments with integers from $1$ to $n$. It is known that gifts in the first store of the $i$-th department cost $a_i$ rubles, and in the second store of the $i$-th department, they cost $b_i$ rubles.

Upon entering the shopping center, Sasha will visit each of the $n$ departments, and in each department, he will enter exactly one store. Thus, when Sasha enters the $i$-th department, he will perform exactly one of two actions:

1. Buy a gift for the first girlfriend, spending $a_i$ rubles.
2. Buy a gift for the second girlfriend, spending $b_i$ rubles.

Sasha intends to buy at least one gift for each girlfriend. Moreover, he wants to choose the gifts in such a way that the difference between the prices of the most expensive gifts bought for each girlfriend is as small as possible, so that no one feels offended.

More formally: let $m_1$ be the maximum price of a gift bought for the first girlfriend, and $m_2$ be the maximum price of a gift bought for the second girlfriend. Sasha wants to choose the gifts to minimize the value $|m_1 - m_2|$.

Input

The first line contains a single integer $n$ ($2 \le n \le 500\,000$) — the number of departments in the shopping center.

Each of the following $n$ lines contains two integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 10^9$) — the prices of the gifts in the first and second store of the $i$-th department, respectively.

Output

Output a single integer — the minimum difference between the prices of the most expensive gifts bought for the girlfriends.

Examples

Input 1

2
1 2
2 1

Output 1

0

Input 2

5
1 5
2 7
3 3
4 10
2 5

Output 2

1

Note

In the first example, Sasha has two possible courses of action: buy a gift for the first girlfriend in the first department and for the second girlfriend in the second department, or vice versa. In the first case, $m_1 = m_2 = 1$, and in the second case, $m_1 = m_2 = 2$. In both cases, the answer is $0$.

In the second example, one can buy gifts for the first girlfriend in the 2nd, 4th, and 5th departments, and for the second girlfriend in the 1st and 3rd departments. Thus, $m_1 = \max(2, 4, 2) = 4$, $m_2 = \max(5, 3) = 5$. The answer is $|4 - 5| = 1$.

Subtasks

The tests for this problem consist of 5 groups. Points for each group are awarded only if all tests in the group and all tests in certain previous groups are passed.