Description

Wind has designed many robots. However, each believes itself to be the strongest, and thus, a competition begins...

The robots want to determine who is the most agile, so they organize the following competition. First, they are presented with a row of $n$ numbers. The challenge is to quickly write down the maximum and minimum values of every consecutive $k$ numbers. Of course, these robots operate at high speeds, so the competition is about who can write the answers the fastest.

But Wind also wants to know the answers. Can you help him?

Input Format

The first line contains $n$ and $k$, as described in the problem statement.

The second line contains $n$ numbers, representing the numerical sequence. All numbers fall within the range of Pascal's longint, meaning all numbers are integers within $[-2^{31}, 2^{31}-1]$.

Output Format

There should be $n-k+1$ lines of output. The $i$-th line should display the maximum and minimum values of the $k$ numbers from the $i$-th to the $(i+k-1)$-th position.

Sample 1

5 3
1 2 3 4 5

3 1
4 2
5 3

Data Range and Hint

For all data, $1\le k\le n\le 10^5$.