题目描述

小 W 有 $N$ 堆糖果，每堆有 $a_i$ 个。现在，他要把这 $N$ 堆糖果分别分给 $N$ 个小朋友。为了使每个小朋友被分到的糖果数尽量均匀，小 W 每次会按顺序执行以下操作： 1. 找到糖果数量最多的糖果堆（如果多于一个，则随机选择一个），从中取出一颗糖果； 2. 在剩下各堆糖果中(包含前面取出糖果的那堆)找到糖果数量最少的糖果堆（如果多于一个，则随机选择一个），将刚刚取出的糖果放入这堆糖果中。

现在，小 W 想请你帮他计算，$K$ 次操作后，最终被分到糖果最多的小朋友与最少的小朋友，他们得到的糖果数之差（即操作后糖果最多的糖果堆中的糖果数与糖果最少的糖果堆中的糖果数之差）。

输入输出格式

输入格式

从文件 candies.in 中读入数据。

输入包含多组测试数据。

第一行包含一个正整数 $T$ ，表示该测试点的测试数据组数。

对于每组测试数据，第一行包含两个正整数 $N,K$ ，表示糖果的堆数和小 W 要进行的操作次数；第二行包含 $N$ 个正整数 $a_i$ ，表示每堆糖果初始时的糖果数。

输出格式

输出到文件 candies.out 中。

对于每个测试数据，输出一行包含一个正整数，表示该组测试数据的答案。

样例输入和输出

样例输入 1

2
4 100
1 1 10 10
4 3
2 2 2 2

样例输出 1

1
0

数据范围

对于 $10\%$ 的数据，$N\leq 500, K\leq 40000, a_i\leq 500$ ；

对于 $30\%$ 的数据，$N\leq 1000, K\leq 1.5\times 10^5, a_i\leq 1000$ ；

对于 $50\%$ 的数据， $N\leq 10000, K\leq 2\times 10^7, a_i\leq 10^5$ ；

对于 $100\%$ 的数据，$1\leq N\leq 10^5, 1\leq K \leq 1\times 10^{15}, 1\leq a_i\leq 10^9$ 。