Consider a sequence of K elements; we can calculate its difference sequence by taking the difference between each pair of adjacent elements. For instance, the difference sequence of {5, 6, 3, 9, -1} is {6 - 5, 3 - 6, 9 - 3, -1 - 9} = {1, -3, 6, -10}. Formally, the difference sequence of the sequence a[1], a[2] ... a[k] is b[1], b[2] ... b[k-1], where b[i] = a[i + 1] – a[i]. The derivative sequence of order N of a sequence A is the result of iteratively applying the above process N times. For example, if A = {5, 6, 3, 9, -1}, the derivative sequence of order 2 is: {5, 6, 3, 9, -1} → {1, -3, 6, -10} → {-3-1, 6-(-3), -10-6} = {-4, 9, -16}. You will be given k (1 <= k <= 20) and N (0 <= N <= k - 1) followed by k integers. Your task is to write a program to output a sequence representing the derivative sequence of order N of a.

Example

Input:
5 1
5 6 3 9 -1
5 2
5 6 3 9 -1
5 4
5 6 3 9 -1
8 3
4 4 4 4 4 4 4 4
2 0
-100 100

Output:
1 -3 6 -10 
-4 9 -16 
-38 
0 0 0 0 0 
-100 100