The k-th Shrink Factor in the Print Shop

A print shop stocks paper in the distinct widths sizes, sorted ascending. Shrinking a picture from width sizes[j] down to a smaller width sizes[i] (so i < j) uses the shrink factor sizes[i] / sizes[j]. Every pair i < j gives one factor, so there are n * (n - 1) / 2 of them, and equal values from different pairs are counted separately.

Sort all these factors in ascending order and return the k-th one (1-based) as a reduced fraction [p, q] with gcd(p, q) = 1.

Examples

Input:  sizes = [1, 2, 3, 5], k = 3
Output: [2, 5]
Explanation: the factors in order are 1/5, 1/3, 2/5, 1/2, 3/5, 2/3.

Input:  sizes = [1, 2, 3, 4, 6], k = 6
Output: [1, 2]
Explanation: in order: 1/6, 1/4, 1/3, 2/6, 1/2, 2/4, 3/6, 2/3, 4/6, 3/4.
The 5th, 6th and 7th factors all equal 1/2.

Constraints

• 2 <= len(sizes) <= 8000; the widths are distinct and sorted ascending
• 1 <= sizes[i] <= 30000
• 1 <= k <= n * (n - 1) / 2
• There can be over 30 million factors; listing them all is too slow for the largest tests.

Goals

• Rank the values of an implicit sorted set without listing it
• Count fractions below a threshold with one moving pointer and exact integer comparisons