Cho một dãy ~A~ gồm ~N~ phần tử được đánh số từ ~1~ đến ~N~. Phần tử thứ ~i~ có giá trị là ~A_i~. Cho ~k~ là một số nguyên dương (~k ≤ N~). Với mỗi phần tử ~i~ (~k ≤ i ≤ N~), tìm giá trị nhỏ nhất và lớn nhất của các phần tử trong đoạn từ ~i - k + 1~ đến ~i~ trên dãy ~A~.

• ~\text{minRange}_i = min(A_{i-k+1},\ldots,A_i)~;
• ~\text{maxRange}_i = max(A_{i-k+1},\ldots,A_i)~.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương ~N, k\ (1\le k \le N \le 10^5)~;
• Dòng sau chứa ~N~ số nguyên ~A_1, A_2, … , A_N\ (|A_i| ≤ 10^9)~.

Dữ liệu ra:

• In ra ~N - k + 1~ dòng, dòng thứ ~i~ là giá trị nhỏ nhất ~minRange_i~ và lớn nhất ~maxRange_i~.

Ví dụ:

Dữ liệu vào:

8 4 
1 3 5 7 4 5 9 5

Dữ liệu ra:

1 7
3 7
4 7
4 9
4 9