Description

There is a sequence $a$ of length $n$ and a window of size $k$. The window slides from left to right, moving one position at a time. After each slide, find the minimum and maximum values within the window.

For example, for the sequence $[1,3,-1,-3,5,3,6,7]$ and $k = 3$, the process is as follows:

$$\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{Window position} & \textsf{Minimum} & \textsf{Maximum} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array}$$

Input Format

The input has two lines. The first line contains two positive integers $n, k$.
The second line contains $n$ integers representing the sequence $a$.

Output Format

Output two lines. The first line contains the minimum of the window after each slide.
The second line contains the maximum of the window after each slide.

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

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

Hint

[Constraints]
For 50% of the testdata, $1 \le n \le 10^5$.
For 100% of the testdata, $1 \le k \le n \le 10^6$, $a_i \in [-2^{31}, 2^{31})$.

Translated by ChatGPT 5