Description

给你一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，如下表所示：

你的任务是找出窗体在各个位置时的最大值和最小值。

Format

Input

第1行为n，k。
第2行为长度为n的数组。（<=2×10^9）

Output

共2行，第1行是每个位置的min value，第2行是每个位置的max value。每个数之间用空格隔开

Sample 1

Input

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

Output

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

Limitation

1s, 64MiB for each test case.

【数据规模】
对于20%的数据，K<=N<=1 000；
对于50%的数据，K<=N<=100 000；
对于100%的数据，K<=N<=1 000 000；

Source

poj2823