C. Farthest Apart
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sanjay is focusing on proposing questions. He wants to ensure that he and his soulmate are as far apart as possible on a 1D line. He needs your help to solve this problem optimally.

On a 1D line, two people are at Sanjay $$$(x_1)$$$ and his soulmate $$$(x_2)$$$ with $$$x_1 \lt x_2$$$.

Initially you have $$$n$$$ pairs $$$(l, r)$$$ such that $$$l \leq r$$$, $$$l \leq x_2$$$, and $$$x_1 \leq r$$$.

For each pair, you can perform:

  1. $$$x_1 = \max(x_1, l)$$$,
  2. $$$x_2 = \min(x_2, r)$$$.

Additionally, exactly once, you must perform both operations (1) and (2) on the same pair. For the remaining pairs, you must choose to perform either operation (1) or (2).

Your task is to find the maximum possible value of $$$x_2 - x_1$$$ after performing the operations optimally, ensuring that Sanjay and his soulmate are as far apart as possible.

Input
  • The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of pairs.
    • The second line contains two integers $$$x_1$$$ and $$$x_2$$$ $$$(0 \leq x_1 \lt x_2 \leq 10^9)$$$ — the initial positions of Sanjay and his soulmate.
    • The next $$$n$$$ lines each contain two integers $$$l$$$ and $$$r$$$ $$$(0 \leq l \leq r \leq 10^9, l \leq x_2, x_1 \leq r)$$$ — the ranges of the pairs.
The sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.
Output
  • For each test case, print a single integer — the maximum possible value of $$$x_2 - x_1$$$.
Example
Input
2
2
2 9
1 8
3 7
3
10 60
11 58
12 59
13 59
Output
5
47
Note
  • For Test Case $$$1$$$: The maximum possible value of $$$x_2$$$ - $$$x_1$$$ is achieved by applying both operations $$$1$$$ and $$$2$$$ on $$$(1, 8)$$$ , choosing operation $$$1$$$ for the remaining all pairs, resulting in maximum value $$$x_2$$$ - $$$x_1$$$ = $$$5$$$.