H. Broken Heart
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The night before Valentine's Day, Randy made a very large chocolate heart to give to his special someone. However, Randy dropped it on the ground by accident, causing the heart to split into a left piece and a right piece.

Unfortunately, some tiny pieces of the heart seem to have been lost after the accident, so Randy is having a hard time putting the heart back together. The broken edges along each piece each have a jagged region that needs to be fit together somehow.

More formally, the jagged edge along the left piece and the edge along the right piece can be described by two sequences $$$\{ l_1, l_2, ..., l_n \}$$$ and $$$\{ r_1, r_2, ..., r_n \}$$$, respectively. In particular, a sequence $$$\{ a_1, a_2, ..., a_n \}$$$ represents an edge consisting of the following line segments in the 2D plane:

  • $$$(a_1, -\infty)$$$ to $$$(a_1, 1)$$$,
  • $$$(a_i, i)$$$ to $$$(a_{i + 1}, i + 1)$$$ for all $$$1 \le i \lt n$$$,
  • and $$$(a_n, n)$$$ to $$$(a_n, \infty)$$$.

To fit the two pieces together, Randy can move the left piece as far up or down as he wishes. He will then move this piece as far to the right as possible, until it intersects with the right piece at any point(s) or line segment(s). Randy wants to know: if he moves the left piece up/down optimally, what is the maximum distance he can shift that piece rightward?

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) – the size of the sequences describing the jagged edges.

The second line contains $$$n$$$ space-separated integers, with the $$$i$$$-th integer being $$$l_i$$$ ($$$-10^6 \le l_i \le 10^6$$$).

The third line contains another $$$n$$$ space-separated integers, with the $$$i$$$-th integer being $$$r_i$$$ ($$$-10^6 \le l_i \le r_i \le 10^6$$$).

Output

If Randy cannot move the left piece in the positive $$$x$$$-direction at all, output $$$0$$$.

Otherwise, output two relatively prime positive integers $$$p$$$ and $$$q$$$ representing the maximum possible displacement $$$\frac{p}{q}$$$.

Examples
Input
4
4 1 4 4
7 6 6 7
Output
5 2
Input
1
0
0
Output
0
Note

In the first sample test case (see picture above), Randy can move the left piece up $$$\frac{1}{2}$$$ units and right $$$\frac{5}{2}$$$ units to achieve the maximum displacement in the positive $$$x$$$-direction.

In the second sample test case, the two edges are both flat and flush against each other. Randy cannot move the left piece to the right any further.