Description

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

你的任务是找出窗口在各位置时的max value,min value.

Input Format

第1行n,k,第2行为长度为n的数组

Output Format

2行，第1行每个位置的min value,第2行每个位置的max value

Sample

Input

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

Output

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

Hint

n<=1000000