First Negative Number in Every Window

Mediumjavapythonccppjavascript

Given an integer array and a window size K, find the first negative number in every contiguous window of size K. If a window has no negative number, use 0 for that window.

Input Format

The first line contains two integers N and K. The second line contains N space-separated integers.

Output Format

Print the first negative value from each window (left to right), separated by single spaces.

Example 1

Input

8 3
12 -1 -7 8 -15 30 16 28

Output

-1 -1 -7 -15 -15 0

Explanation: For each group of three consecutive elements, take the first negative number.

Input (stdin)

Output

Run your code to see output here...