#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Ranald was given an array of *N* integers, *A*. He decides to compress it by applying the following algorithm: take every consecutive segment of *K* elements and take the maximum. Then create a new array *B* of length (*N* - *K* + 1), where the *i*th element of this array would represent the maximum element within *A _{i}* and

*A*.

_{i+K-1}Unfortunately, Ranald lost his original array! Given the new array *B*, help Ranald reconstruct his original array. If there are more than one possible answers, output any.

## Input

The first line of input will contain two integers, *N* and *K*.

The second line of input will contain (*N* - *K* + 1) integers, representing the array *B*.

## Output

The output should contain one line with *N* integers, representing the array *A*. All integers should be within 1 and 10^{9}.

## Limits

For all subtasks: 1 ≤ K ≤ N ≤ 300 000, 1 ≤ B_{i} ≤ 10^{9}.

Subtask 1 (4%): K = 1.

Subtask 2 (16%): N ≤ 8.

Subtask 3 (13%): K = 2.

Subtask 4 (18%): B_{i} ≤ 2.

Subtask 5 (23%): N ≤ 1 000.

Subtask 6 (26%): No additional constraints.

Subtask 7 (0%): Sample Testcases.

## Sample Input 1

5 3 6 6 4

## Sample Output 1

5 6 1 3 4

## Sample Input 2

7 2 6 6 5 5 5 2

## Sample Output 2

1 6 2 4 5 1 2

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 4 | 20 | 1s | 256MB | Minimum |

2 | 16 | 22 | 1s | 256MB | Minimum |

3 | 13 | 21 | 1s | 256MB | Minimum |

4 | 18 | 20 | 1s | 256MB | Minimum |

5 | 23 | 42 | 1s | 256MB | Minimum |

6 | 26 | 122 | 1s | 256MB | Minimum |

7 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o decompress -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512