Sequence Transformation

Interview

Time limit2sMemory limit128 MB

Summary

Repeatedly replace a sequence with its adjacent differences K times and print the resulting shorter sequence.

Level: Easy2 of 10
Topics: Array, Simulation, Implementation
Solved: No attempts yet

Problem

You are given a sequence A of length N. In one transformation, create a new sequence from the differences of adjacent elements. The new sequence B has length one less than the previous sequence, and B[i] = A[i+1] - A[i].

Given the initial sequence, output the sequence that remains after applying this transformation K times.

Input

The first line contains N and K. N is a positive integer not greater than 20, and K is an integer from 0 to N-1.

The second line contains N integers separated by commas (,). Each integer has absolute value at most 100.

Output

Print the sequence after K transformations on one line, with its values separated by commas (,).

Examples5

Example 1
Input
```
5 1
5,6,3,9,-1
```
Expected output
```
1,-3,6,-10
```
Example 2
Input
```
5 2
5,6,3,9,-1
```
Expected output
```
-4,9,-16
```
Example 3
Input
```
5 4
5,6,3,9,-1
```
Expected output
```
-38
```
Example 4
Input
```
8 3
4,4,4,4,4,4,4,4
```
Expected output
```
0,0,0,0,0
```
Example 5
Input
```
2 0
-100,100
```
Expected output
```
-100,100
```