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 ith element of this array would represent the maximum element within Ai and Ai+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 109.
Limits
For all subtasks: 1 ≤ K ≤ N ≤ 300 000, 1 ≤ Bi ≤ 109.
Subtask 1 (4%): K = 1.
Subtask 2 (16%): N ≤ 8.
Subtask 3 (13%): K = 2.
Subtask 4 (18%): Bi ≤ 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