Cửa Sổ Phép Thuật

Giáo sư Dumbledore đã lắp đặt một hệ thống cảm biến dọc theo hành lang Hogwarts để đo năng lượng phép thuật. Hệ thống ghi nhận được $N$ giá trị năng lượng liên tiếp $a_1,a_2,\dots ,a_N$.

Để phân tích biến động năng lượng, giáo sư dùng một cửa sổ quan sát có độ rộng $K$. Cửa sổ trượt từ trái sang phải, mỗi lần dịch đúng một vị trí. Tại mỗi vị trí, giáo sư cần biết giá trị năng lượng nhỏ nhất và lớn nhất trong cửa sổ.

Hãy giúp giáo sư tính toán kết quả cho tất cả các vị trí của cửa sổ.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $K$ — số giá trị năng lượng và độ rộng cửa sổ.
• Dòng thứ hai: $N$ số nguyên $a_1,a_2,\dots ,a_N$ — các giá trị năng lượng.

Dữ liệu ra

• Dòng đầu: $N-K+1$ số nguyên cách nhau bởi dấu cách — giá trị nhỏ nhất của mỗi cửa sổ.
• Dòng thứ hai: $N-K+1$ số nguyên cách nhau bởi dấu cách — giá trị lớn nhất của mỗi cửa sổ.

Ràng buộc

• $1\le K\le N\le {10}^6$
• $|a_i|\le {10}^9$

Ví dụ