CF671B.Robin Hood

We all know the impressive story of Robin Hood. Robin Hood uses his archery skills and his wits to steal the money from rich, and return it to the poor.

There are n citizens in Kekoland, each person has c__i coins. Each day, Robin Hood will take exactly 1 coin from the richest person in the city and he will give it to the poorest person (poorest person right after taking richest's 1 coin). In case the choice is not unique, he will select one among them at random. Sadly, Robin Hood is old and want to retire in k days. He decided to spend these last days with helping poor people.

After taking his money are taken by Robin Hood richest person may become poorest person as well, and it might even happen that Robin Hood will give his money back. For example if all people have same number of coins, then next day they will have same number of coins too.

Your task is to find the difference between richest and poorest persons wealth after k days. Note that the choosing at random among richest and poorest doesn't affect the answer.

我们都知道罗宾汉那令人印象深刻的传奇故事。罗宾汉凭借其精湛的射箭技艺与过人的智慧，从富人手中夺取钱财，并将其分发给穷人。

克克兰德（Kekoland）共有 $n$ 位市民，每人拥有 $c_i$ 枚硬币。每天，罗宾汉都会从当天最富有的市民那里恰好取走 1 枚硬币，并将其交给当天最贫穷的市民（即在从最富有者处取走 1 枚硬币后，剩余最贫穷者）。若最富有者或最贫穷者不唯一，他将从中随机选择一位。遗憾的是，罗宾汉已年迈，计划在 $k$ 天后退休，他决定将这最后的 $k$ 天用于帮助穷人。

在罗宾汉取走硬币后，原先最富有的人可能变为最贫穷者；甚至可能出现罗宾汉将硬币“还给”同一个人的情形。例如，若所有人初始硬币数相同，则第二天他们的硬币数仍将完全相同。

你的任务是：求出 $k$ 天后，最富有者与最贫穷者财富之差。注意：在最富有者或最贫穷者不唯一时的随机选择，不会影响最终答案。

The first line of the input contains two integers n and k (1 ≤ n ≤ 500 000, 0 ≤ k ≤ 109) — the number of citizens in Kekoland and the number of days left till Robin Hood's retirement.

The second line contains n integers, the i-th of them is c__i (1 ≤ c__i ≤ 109) — initial wealth of the i-th person.

输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 500\,000$，$0 ≤ k ≤ 10^9$）—— 分别表示 Kekoland 的公民人数以及距离罗宾汉退休还剩下的天数。

第二行包含 $n$ 个整数，其中第 $i$ 个数为 $c_i$（$1 ≤ c_i ≤ 10^9$）—— 表示第 $i$ 位公民的初始财富。

Print a single line containing the difference between richest and poorest peoples wealth.

输出一行，包含最富有人与最贫穷者财富的差值。

Lets look at how wealth changes through day in the first sample.

1. [1, 1, 4, 2]
2. [2, 1, 3, 2] or [1, 2, 3, 2]

So the answer is 3 - 1 = 2

In second sample wealth will remain the same for each person.

我们来看一下在第一个样例中，财富在一天之内的变化情况。

1. [1, 1, 4, 2]
2. [2, 1, 3, 2] 或 [1, 2, 3, 2]

因此答案为 $3 - 1 = 2$。

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