Problem Description
You are given an array that consists of n integer numbers. You have to change at most K elements of this array, so that the resulting array will be a arithmetic progression. From all the possible arithmetic progressions, you
should choose most beautiful.
You can uniquely define the arithmetic progression by two numbers a0 and d - the first element of the given progression and the step that defines next element. (ai = a0+i * d). The progression A(a0 , d0) is more beautiful than the progression B(b0, d1) iff
(a0 < b0 or (a0 = b0 and d0 < d1))
Input
The first line contains two integers N and K denoting the number of elements in the given array and the number of elements that you can change
The second line contains N space-separated integers A1, A2, ..., AN denoting the given array.
Output a single line containing the resulting array with at most K changes. Mind that among all the arithmetic sequences you have to choose the most beautiful.
In the given test data, it is always possible to recover at least one arithmetic progression under the constraints of the problem.