Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

Input

the number n denoting number of elements in the array then after a new line we have the numbers of the array and then k in a new line

n < 10⁶
k < 10⁵
1 ≤ k ≤ n

and each element of the array is between 0 and 10⁶

(Edited: In fact, n ≤ 10⁵)

Output

print the output array

Example

Input:
9
1 2 3 1 4 5 2 3 6
3
Output:
3 3 4 5 5 5 6