A sensor emits n non-negative integer samples one at a time. You maintain a sliding window of the most recent k samples (fewer than k while the stream is still filling up). After receiving each sample, output the floor of the average of all samples currently held in the window.

Concretely, after receiving sample number t (1-indexed), the window holds the last min(t, k) samples; output floor(sum_of_window / size_of_window). Because all samples are non-negative, this floor equals integer division.

Input format

Line 1: two integers n and k. Line 2: n space-separated non-negative integers, the samples in arrival order.

Output format

One line with n space-separated integers: after each sample, the floor of the current window average.

Constraints

• 1 <= n <= 100000
• 1 <= k <= 100000 (k may be larger than n)
• 0 <= each sample <= 1000000000

5 3
1 2 3 4 5

1 1 2 3 4

3 5
4 4 4

4 4 4