Maroof is visiting a new city. Being a Mathematician, he does not like to visit different places but visit places differently. The city has N places to visit. We are given the (X,Y) co-ordinates of the places to visit. Maroof wants to start from a random place i and want to go to a random place j. But he involved a little maths in his procedure. Following are his demands:

He will give a number A. Now, the place i and place j should be such that the line connecting these two points must have the Ath maximum slope (There are total N*(N-1)/2 possible slopes among all the unordered places pairs).

Input arguments to your function:

Integer A

B : An integer array containing X-coordinates of the places

C : An integer array containing Y-coordinates of the places

Note that the length of B (= N) will be equal to the length of C and the ith point is represented by `(B[i], C[i])`

.

Output: An array having exactly 2 elements : numerator and denominator of the slope (fraction should not be further reducible).

Additional instructions:

Places can be overlapping (Two places can have same (X,Y) co-ordinates)

Overlapping places must not be considered as same places.

In case the line joining the places is vertical, slope is -INF.

Two overlapping places have slope -INF.

Constraints:

1 <= A <= 70

1 <= N <= 100,000

-10^9 <= B[i], C[i] <= 10^9 (Also X and Y coordinates can only be Integers)

Example:

Input: A = 2

B = [1, 2, 3, 1, 2] //X coordinates of the places

C = [2, 4, 6, 2, 3] //Y coordinates of the places

Output:

ans = [2,1].

Sorted Points = [(1,2), (1,2), (2,4),(2,3),(3,6)]

SortedSlopes: [3, 2, 2, 2, 2, 2, 1 , 1, -INF, -INF]

Output instructions:

Output fraction should not be further reducible [e.g. Reduce (6,4) to (3,2) before returning the answer]

In case the answer is negative infinity, return (-1,0)

In case the answer is zero, return (0,1)

In case the answer is negative, numerator must be negative. [e.g.: (-3,2) not (3,-2) ]

Any idea how to solve it in linear or linear log time.