Description

Original Source: POJ 2823

Given an array of length $N$, a sliding window of size $K$ moves from the far left to the far right. You can only see the $K$ numbers in the window at any time. Each time the window moves one position to the right, as shown below:

Your task is to determine the maximum and minimum values in the sliding window at every position.

Input Format

Line 1: Two integers $N$ and $K$;
Line 2: $N$ integers representing the elements of the array ($≤2\times 10^9$);

Output Format

The first line contains the minimum values as the sliding window moves from left to right, with each number separated by a space;
The second line contains the maximum values as the sliding window moves from left to right, with each number separated by a space.

Sample 1

8 3
1 3 -1 -3 5 3 6 7

-1 -3 -3 -3 3 3
3 3 5 5 6 7

Constraints & Hints

For $20\%$ of the data, $K≤N≤1000$;
For $50\%$ of the data, $K≤N≤10^5$;
For $100\%$ of the data, $K≤N≤10^6$.