Percentiles of the Fun Run

The results page of a charity fun run shows percentiles of the finishing times (in seconds): "90% of runners finished within ... seconds". The organisers use this rule for the p-th percentile of n times:

1. Sort the times in increasing order: s[0] <= s[1] <= ... <= s[n-1].
2. Compute the position pos = p / 100 * (n - 1).
3. Let k be the whole part of pos and f = pos - k. The percentile is s[k] + f * (s[k+1] - s[k]), or simply s[k] when k is the last index.

So the 0th percentile is the fastest time, the 100th the slowest, and a position halfway between two runners gives the value halfway between their times.

Write percentiles(times, ps) that returns a list with the p-th percentile for every p in ps, in the same order as ps. The list times must not be changed.

Examples

Input:  times = [1510, 1320, 1805, 1440, 1600], ps = [0, 25, 50, 90, 100]
Output: [1320.0, 1440.0, 1510.0, 1723.0, 1805.0]
Explanation: sorted: 1320, 1440, 1510, 1600, 1805. For p = 90 the position is
0.9 * 4 = 3.6, so the value is 1600 + 0.6 * (1805 - 1600) = 1723.

Input:  times = [2000], ps = [10, 99]
Output: [2000.0, 2000.0]

Constraints

• 1 <= len(times) <= 10**5, 1 <= len(ps) <= 100
• every time is a whole number of seconds with 600 <= time <= 10**4
• every p is a number with 0 <= p <= 100
• floats are compared with a tolerance of 1e-6

Goals

• Sort once and read several percentiles from the sorted copy
• Turn a percentage into a position in the sorted list
• Interpolate between two neighbouring values when the position is not whole