我们都知道阿凡提的传奇故事。阿凡提经常用他的智慧劫富济贫。

德清有n个市民，每人 c_i 块钱。每天阿凡提都会从最富有的人那里拿一块钱给最穷的那个人。如果不止一个最穷的人，则随机选择一位。不幸的是，阿凡提老了，他想在k天后退休。阿凡提决定在最后这几天中尽力帮助穷人们。

当阿凡提拿走钱后，最富有的人也可能变成最穷的人，甚至可能会发生偷来的钱给了被偷的那个人的情况。假如所有人拥有相同数量的硬币，那么第二天他们也会拥有同样数量的硬币。

你的任务是找出在k天后最富有的人与最贫穷的人之间的差距。注意，在最富有的人和最贫穷的人中随机选择并不影响答案。

第一行包含两个整数n,k(1 ≤ n ≤ 500 000, 0 ≤ k ≤ 10⁹)——德清的公民数和阿凡提未退休的天数。

第二行包含n个整数，第i个的值为c_i (1 ≤ c_i ≤ 10⁹)——第i个人的硬币数。

最富有的人和最贫穷的人之间的差距。

样例2输入

3 1
2 2 2

样例2输出

0

注释：

在第一个样本中，让我们看看财富在一天中是如何变化的。

1. [1，1，4，2]

2. [2，1，3，2]或[1，2，3，2]

所以答案是3-1=2

在第二个样本中，每个人的财富将保持不变。

华羽圣2021