Robin Hood

Có $n$ người dân, người thứ $i$ ban đầu có $c_i$ đồng xu.

Mỗi ngày diễn ra đúng một lần chuyển: lấy $1$ đồng xu của người giàu nhất (người đang có nhiều xu nhất) và đưa cho người nghèo nhất (người đang có ít xu nhất, xét sau khi đã lấy xu của người giàu nhất). Nếu có nhiều người cùng giàu nhất hoặc cùng nghèo nhất thì chọn tuỳ ý một người trong số đó, cách chọn này không ảnh hưởng đến kết quả.

Sau đúng $k$ ngày, hãy tính hiệu số xu giữa người giàu nhất và người nghèo nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$.

Dữ liệu ra

• Một số nguyên duy nhất: hiệu giữa số xu của người giàu nhất và người nghèo nhất sau $k$ ngày.

Ràng buộc

• $1\le n\le 500000$
• $0\le k\le {10}^9$
• $1\le c_i\le {10}^9$

Ví dụ