滴答

题目描述

仓库中有 $n$ 堆货物，第 $i$ 堆有 $a_i$ 个箱子。一个机器人将执行 $m$ 次操作来使货堆变得平均。

每次操作如下：

• 机器人从当前箱子数最多的一堆中拿出一个箱子。
• 然后将这个箱子放到当前箱子数最少的一堆中。

如果存在多个箱子数最多的堆或最少的堆，机器人可以任意选择其中一个。当所有堆的箱子数都相同时，拿出的箱子会放回原来的堆，这也被视为一次合法的操作。

请问，在完成所有 $m$ 次操作后，箱子数最多的堆和最少的堆之间的数量之差是多少？

输入格式

第一行输入一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行输入两个整数 $n, m$，分别表示货物堆数和操作次数。 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每堆货物的初始箱子数。

输出格式

对于每组测试数据，输出一行一个整数，表示最终的最大堆与最小堆的数量之差。

样例

样例输入

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]：

• m=1: 操作 1 次。从 5 移到 1，变为 [2, 2, 3, 4, 4]。差值为 $4-2=2$。
• m=2: 操作 2 次。从 [2, 2, 3, 4, 4] 开始，从 4 移到 2，变为 [3, 2, 3, 4, 3]。差值为 $4-2=2$。
• m=3: 操作 3 次。从 [3, 2, 3, 4, 3] 开始，从 4 移到 2，变为 [3, 3, 3, 3, 3]。差值为 $3-3=0$。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 100$
• $1 \le n \le 2 \times 10^5$
• $0 \le m \le 10^{18}$
• $0 \le a_i \le 10^9$
• 所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。