这是问题的困难版本。版本之间的唯一区别是 $$$n$$$、$$$k$$$、$$$a_i$$$ 的约束以及所有测试用例的 $$$n$$$ 总和。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
注意异常的内存限制。
给定一个整数数组 $$$a_1、a_2、\ldots、a_n$$$,长度为 $$$n$$$,以及一个整数 $$$k$$$。
长度为 $$$n$$$ 的整数数组 $$$p_1, p_2, \ldots, p_n$$$ 的成本为 $$$$$$\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).$$$$$$
这里,$$$\lfloor \frac{x}{y} \rfloor$$$表示$$$x$$$除以$$$y$$$的整数部分。求数组 $$$p$$$ 的最小成本,使得 $$$1 \le p_i \le k$$$ 对于所有 $$$1 \le i \le n$$$ 而言。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 10^5$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - 满足上述条件的数组 $$$p$$$ 的最小可能成本。
示例
输入 #1
7 5 2 4 5 6 8 11 5 12 4 5 6 8 11 3 1 2 9 15 7 3 2 3 5 5 6 9 10 6 56 54 286 527 1436 2450 2681 3 95 16 340 2241 2 2 1 3
输出 #1
2 0 13 1 4 7 0
注意
在第一个测试用例中,最佳数组是 $$$p = [1, 1, 1, 2, 2]$$$。 $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ 的值数组为 $$$[4, 5, 6, 4, 5]$$$。 $$$p$$$ 的成本为 $$$\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2$$$。我们可以证明不存在成本更小的数组(满足语句中的条件)。
在第二个测试用例中,最佳数组之一是 $$$p = [12, 12, 12, 12, 12]$$$,这导致所有 $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ 均为 $$$0$$$。
在第三个测试用例中,唯一可能的数组是 $$$p = [1, 1, 1]$$$。