Smoothing out a list You should write a program or function which takes a non-negative integer k and a sorted integer list Las input and outputs or returns a smoothed list M.

M is created from the ascending list L by inserting at most k integer elements while keeping the list sorted. The inserted integers should be chosen in a way that the maximum forward difference of M will be as small as possible. We will call this smallest value "smoothness".

The forward differences of the list -1 3 8 11 15 are 4 5 3 4 and the maximum forward difference is 5.

With 2 insertions the smoothness of 2 10 15 is 4 and a possible output is 2 6 10 11 15 with forward differences 4 4 1 4.

Input


A non-negative integer k.
An ascending integer list L with at least 2 elements.


Output


The ascending integer list M.
If multiple correct answers exists output exactly one of them (any one is sufficient).
Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).


Examples

Input (k, L) => A possible output and the maximum forward difference (which is not part of the output) in parentheses

0, 10 20 =&gt; 10 20 (10)

2, 1 10 =&gt; 1 4 7 10 (3)

2, 2 10 15 =&gt; 2 6 10 11 15 (4)

3, 2 10 15 =&gt; 2 5 8 10 12 15 (3)

5, 1 21 46 =&gt; 1 8 15 21 27 33 39 46 (7)

5, 10 20 25 33 =&gt; 10 14 18 20 24 25 29 33 (4)

3, 4 4 6 9 11 11 15 16 25 28 36 37 51 61 =&gt; 4 4 6 9 11 11 15 16 22 25 28 36 37 45 51 59 61 (8)

15, 156 888 2015 =&gt; 156 269 382 495 608 721 834 888 1001 1114 1227 1340 1453 1566 1679 1792 1905 2015 (113)

8, -399 -35 -13 56 157 =&gt; -399 -347 -295 -243 -191 -139 -87 -35 -13 39 56 108 157 (52)

5, 3 3 3 =&gt; 3 3 3 3 (0)


This is code-golf so the shortest entry wins.
Python 2, 104

def f(L,k,d=1):
 M=[];p=L[0]
 for x in L:M+=range(p+d,x,d);p=x
 return M[k:]and f(L,k,d+1)or sorted(L+M)


Tries different maximum increments d, starting from 1 and counting up. Fills in gaps of each pair (p,x) of successive elements by taking every d'th number in the gap. If M is longer than the quota allows, recurses to try a higher d. Otherwise, returns a list of the added and original elements, sorted.

This does all the test cases without delay on my machine.