Cho ~n~ khúc gỗ có độ dài lần lượt là ~a_1, a_2, \dots, a_n~. Tại mỗi thao tác ta được phép chọn một khúc gỗ và tách nó ra thành hai khúc gỗ nhỏ hơn khác rỗng có độ dài bất kì. Vậy sau ~k~ thao tác, ta sẽ có ~n+k~ khúc gỗ.

Với mỗi câu hỏi có ~k=1,2,\dots,m~, hãy tìm cách thực hiện ~k~ thao tác sao cho sau cùng, chênh lệch độ dài giữa khúc gỗ dài nhất và khúc gỗ ngắn nhất là nhỏ nhất. Lưu ý, mỗi câu hỏi ~k~ độc lập với nhau.

Input

• Dòng đầu tiên chứa số nguyên ~n, m~ ~(1 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5)~.

• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~ là độ dài ban đầu của từng khúc gỗ.

Output

• In ra ~m~ số nguyên trên một dòng, cách nhau một khoảng trắng là kết quả của mỗi câu hỏi.

Scoring

Sample Input 1

3 3
12 5 4

Sample Output 1

2 1 2