Kth Smallest Prime Fraction

You are given a sorted array arr of 1 and prime numbers, and an integer k.

For every pair of indices i < j, consider the fraction arr[i] / arr[j]. Return the kth smallest such fraction as an array [arr[i], arr[j]].

Examples

Example 1:

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

Output: [2,5]

Explanation: The fractions in order are: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. The 3rd is 2/5.

Example 2:

Input: arr = [1,7], k = 1

Output: [1,7]

Explanation: The only fraction is 1/7.

Example 3:

Input: arr = [1,2,3,5], k = 6

Output: [2,3]

Explanation: The fractions in order are: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. The 6th is 2/3.

Constraints

• 2 <= arr.length <= 1000
• 1 == arr[0]
• arr[i] is prime for i > 0
• All elements of arr are unique.
• 1 <= k <= arr.length * (arr.length - 1) / 2