Caravan Robbers

Long ago, in a faraway land, there were two great cities joined by the Great Caravan Road. Many robber gangs "worked" along that road.

By an old custom, the $i$-th gang robbed every merchant who dared to travel between miles $a_i$ and $b_i$ of the Great Caravan Road. The custom was old but clever: there were no two distinct gangs $i$ and $j$ with $a_i \le a_j$ and $b_j \le b_i$ (that is, no gang's interval contained another's). Still, whenever two gangs' intervals overlapped, bloody fights sometimes broke out.

To end the wars, the gang leaders decided to reassign each gang a new interval so that:

• all new intervals are pairwise non-overlapping (to avoid bloodshed),
• each gang's new interval is a subinterval of its old one (to respect the old custom), and
• all new intervals have the same length (to keep things fair).

Compute the maximum possible common length of the intervals after this redistribution.

The first line contains $n$ ($1 \le n \le 100000$) — the number of gangs.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($0 \le a_i < b_i \le 1000000$), describing one gang's interval. The input satisfies the condition stated above: no gang's interval contains another's.

Output the maximum possible common interval length, in miles, as an irreducible fraction $p/q$.

For the sample with gangs $(2, 6)$, $(1, 4)$, and $(8, 12)$, one optimal redistribution gives every gang an interval of length $5/2$:

• the first gang takes $[7/2, 6] = [3.5, 6]$, a subinterval of its original $(2, 6)$;
• the second gang takes $[1, 7/2] = [1, 3.5]$, a subinterval of its original $(1, 4)$;
• the third gang takes $[8, 21/2] = [8, 10.5]$, a subinterval of its original $(8, 12)$.