关键结论

• 若操作次数足够多，最终状态一定是“尽可能平均”的：差值为 $0$（当总和可整除 $n$）或为 $1$（否则）。
• 我们不直接模拟（$m\le 2\cdot10^9$），而是二分答案：设最终极差为 $D$，判定“是否能在至多 $m$ 次操作内把所有堆压进某个长度为 $D$ 的区间 $[L, L+D]$”即可。

核心做法：二分极差 + 前缀和 O(1) 计算代价

可行性判定（给定 $D$）

我们希望存在某个整数 $L$，把所有 $a_i$ 改造成 $b_i\in[L,L+D]$，且总移动次数 $\le m$。

题目内容

仓库里一大批货到了。它们被杂乱地摆成了 $n$ 堆，第 $i$ 堆有 $a_i$ 个箱子。为了让仓库里的货物尽可能平均，小红型号机器人开始出动了!

小红机器人每接收到一次平均货物的信号，即通讯器的一次“滴答”声，就会自动去把箱子数最多的那一堆，如第 $j$ 堆，拿出一个箱子，然后把这个箱子放到箱子数当前(已经拿走一个箱子后的当前状态)最少的那一堆，如第 $k$ 堆，如果有多个堆箱子数都一样多，任选即可。注意，存在一种情况 $j=k$ (所有堆箱子数相同时)，小红机器人完成这一次操作后相当于没有放置，也是合法的操作。

目前通讯器发出了 $m$ 次滴答声，小红机器人如果完成了所有操作，箱子数最多的堆和箱子数最少的堆数量之差是多少呢?

输入描述

第一行 $1$ 个整数 $T$ ，表示数据组数。

对每组数据，有 $2$ 行。

第一行两个整数 $n$ 和 $m$ ，表示货物堆数，和通讯器的滴答声数量。

第二行 $n$ 个整数 $a_1,a_2,...,a_n$ 表示每堆货物的初始箱子数。

对于 $100$% 的数据：$1≤T≤5，1≤n≤100000，1≤m≤2000000000,1≤a_i≤2000000000$

输出描述

对于每组数据，输出一行一个整数表示答案。

样例1

输入

3
5 1
1 2 3 4 5
5 2
1 2 3 4 5
5 3
1 2 3 4 5

输出

2
2
0

说明

初始箱子为

$1$ $2$ $3$ $4$ $5$

第一次滴答声后变成：

$2$ $2$ $3$ $4$ $4$（第 $5$ 堆搬了一个箱子到了第 $1$ 堆）

此时最大箱子数和最小箱子数之差为 $4-2=2$

第二次滴答声后变成

$2$ $3$ $3$ $4$ $3$（第 $5$ 堆或者第 $4$ 堆搬了一个箱子到第 $1$ 堆或者第 $2$ 堆，注意顺序不同不影响最终答案）

此时最大箱子数和最小箱子数之差为 $4-2=2$

第三次滴答声后变成

$3$ $3$ $3$ $3$ $3$（箱子数为 $4$ 的堆搬了一个箱子到箱子数为 $2$ 的堆）

此时最大箱子数和最小箱子数之差为 $3-3=0$