851. Maximum Element in a Moving Window

0

Hard

Given an array of integers nums with a size of n and a moving window of size k, find the maximum element in the window as it moves from left to right. The window shifts one position to the right each time.

Input Format

The first line contains two integers n and k.

The next line contains n space-separated integers.

The next line contains n space-separated integers.

Output Format

Print the resulting array of maximum elements during each window movement.

Example

Input

4 3
1 3 -1 -3

Output

3 3

Constraints

1 <= n <= 10^5

-10^4 <= a[i] <= 10^4

1 <= k <= n

-10^4 <= a[i] <= 10^4

1 <= k <= n

Loading...

View Submissions

Console