Một hàng rào gồm \(n\) tấm ván thẳng đứng. Chiều rộng của mỗi tấm ván là 1 và chiều cao của chúng có thể khác nhau.

Bạn muốn gắn một tấm quảng cáo hình chữ nhật lên hàng rào. Nhiệm vụ của bạn là tính diện tích lớn nhất của một tấm quảng cáo như vậy trong mỗi cửa sổ gồm \(k\) tấm ván thẳng đứng, từ trái sang phải.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\): chiều rộng của hàng rào và kích thước cửa sổ.

Sau đó có \(n\) số nguyên \(x_1, x_2, \dots, x_n\): chiều cao của từng tấm ván.

Output

In ra \(n - k + 1\) số nguyên: diện tích lớn nhất của các tấm quảng cáo.

Constraints

• \(1 \le k \le n \le 2 \cdot 10^5\)

• \(1 \le x_i \le 10^9\)

Example

8 3
4 1 5 3 3 2 4 1

5 6 9 6 6 4