Kth Smallest Prime Fraction

Given a sorted array of prime numbers starting with 1, return the kth smallest fraction arr[i] / arr[j] with i < j. Use a heap to generate fractions in sorted order without enumerating all pairs.

Input Format

arr = sorted prime-like array, k = rank of fraction

Output Format

fraction [numerator, denominator] that is kth smallest

Constraints

• 2 <= arr.length <= 1000
• arr[0] = 1
• arr is strictly increasing and contains primes thereafter

Examples

arr = [1,2,3,5]
k = 3

[2,5]

arr = [1,7]
k = 1

[1,7]