Cho một dãy có độ dài ~N~, một cửa sổ trượt có độ dài ~K~ di chuyển từ ngoài cùng bên trái sang ngoài cùng bên phải, bạn chỉ có thể thấy ~K~ số trong cửa sổ, mỗi lần cửa sổ trượt di chuyển sang phải một vị trí, như được hiển thị bên dưới:

Nhiệm vụ của bạn là tìm các giá trị lớn nhất và nhỏ nhất trong cửa sổ tại mỗi vị trí.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ là độ dài của dãy và cửa sổ trượt.
• Dòng thứ hai chứa ~N~ số nguyên. ~(\leq 2\times10^9)~.

Dữ liệu ra:

• Dòng đầu tiên cho biết các giá trị nhỏ nhất trong cửa sổ tại mỗi vị trí, lần lượt từ trái sang phải.
• Dòng thứ hai cho biết các giá trị lớn nhất trong cửa sổ tại mỗi vị trí, lần lượt từ trái sang phải.

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 hạn:

• ~20\%~, với ~K\leq N\leq 1000~；
• ~50\%~, với ~K\leq N\leq 10^5~;
• ~100\%~, với ~K\leq N\leq 10^6~.