Cửa sổ trượt (Sliding Window)

Nguồn: POJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $a_1,a_2,\ldots,a_n$ và độ dài cửa sổ $k$. Với mỗi cửa sổ liên tiếp gồm đúng $k$ phần tử, hãy xác định giá trị nhỏ nhất và lớn nhất.

Input

Dòng đầu chứa $n,k$. Dòng thứ hai chứa $n$ số nguyên.

Output

In hai dòng. Dòng đầu là các giá trị nhỏ nhất; dòng thứ hai là các giá trị lớn nhất của các cửa sổ từ trái sang phải.

Subtask

• Subtask 1 (20%): $1 \le n \le 2000$, $1 \le k \le n$.
• Subtask 2 (30%): $1 \le n \le 10^5$, $1 \le k \le n$.
• Subtask 3 (50%): $1 \le n \le 10^6$, $1 \le k \le n$.

Toàn bộ dữ liệu tuân theo: $1 \le k \le n \le 10^6$; các phần tử nằm trong miền số nguyên 32 bit.

Ví dụ

Input

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

Output

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

Giải thích

Với $k=3$, sáu cửa sổ lần lượt cho dãy min $-1,-3,-3,-3,3,3$ và dãy max $3,3,5,5,6,7$.