You are given an array of n integers and a window length k. Slide a window of k consecutive elements from left to right, producing n - k + 1 windows. For each window, report the first negative value that appears in it (scanning the window from left to right). If a window contains no negative value, report 0 for that window.
Because 0 is not negative, it is never itself a valid “first negative” answer, so using 0 as the “no negative present” marker is unambiguous.
Input format
Line 1: two integers n and k separated by a space.
Line 2: n space-separated integers, the array values.
Output format
A single line with n - k + 1 values separated by single spaces: for each window in left-to-right order, its first negative value, or 0 if the window has no negative value.
Constraints
- 1 ≤ k ≤ n ≤ 100000
- -1000000000 ≤ each value ≤ 1000000000
- The answer is uniquely determined.