First Negative Integer In Every Window Of Size K

You have been given an array of integers 'ARR' and an integer ‘K’. You need to find the first negative integer in each window of size ‘K’.

Note :

If a window does not contain a negative integer, then print 0 for that window.

For example :

If N = 9, arr[ ] = {-10, 20, -30, -40, 50, 60, -70, 80, 90} and K = 3

then the output will be
{-10 -30 -30 -40 -70 -70 -70}

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains an integer ‘N’ which denotes the size of the array.

The second line of each test case contains elements of the array. The line consists of values of elements of the array separated by a single space.

The third line of each test case contains an integer ‘K’ which denotes the window size.  

Output Format:

For each test case, print the first negative integer in each window of size ‘K’ separated by a space.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10^2
1 <= N <= 10^3
-10^4 <= data <= 10^4
1 <= K <= N

Where ‘N’ is the size of the array, “data” is the value of the element of the array 'ARR' and ‘K’ is the window size.

Time Limit: 1 sec