题目描述

【部分不宜展示的内容已被删除】

「我們必須立刻改變！從現在起，花果山所有桃樹結下的桃子，直接接收後，再重新分配給花果山上的猴子，直到所有猴子都擁有等量的桃子為止！」

孫悟空要求統計所有猴子所擁有的桃子以及桃樹每天的桃子產量。花果山統計局很快地將相關數據呈給孫悟空：花果山上總共有 $n$ 隻猴子，第 $i$ 隻猴子擁有 $a_i$ 顆桃子，而桃樹的產量很穩定，每天都能夠生產出 $k$ 顆桃子。

花果山的內政大臣天命人針對重新分配的方法，向孫悟空提出建言：「為了花果山上的和諧，重新分配桃子時，不可以從猴子手中奪走任何桃子。每天接收到的桃子，必須當天就分配出去。最重要的是要避免相對剝奪感，每一天分配到最多桃子的猴子，只能比分配到最少桃子的猴子多得一顆桃子。」孫悟空覺得很有道理，便要求按照天命人的建議進行分配。

假設 $n=4,k=7,a_1=1,a_2=2,a_3=3,a_4=4$，即花果山上總共有 4 隻猴子，分別有 1, 2, 3, 4 顆桃子，而桃樹每天的產量是 7 顆桃子。按照天命人的建議，每隻猴子每天都可以分配到一顆或是兩顆桃子，不能更少也不能更多，否則會帶來相對剝奪感。此時可以透過下列步驟，讓所有的猴子擁有等量的桃子：

1. 第一天到第三天都分配各兩顆桃子給前三隻猴子、一顆桃子給第四隻猴子。三天過後，四隻猴子分別擁有 7, 8, 9, 7 顆桃子。
2. 第四天、第五天都分配各兩顆桃子給前兩隻猴子、一顆桃子給第三隻猴子、兩顆桃子給第四隻猴子。五天過後，四隻猴子分別擁有 11, 12, 11, 11 顆桃子。
3. 第六天分配一顆桃子給第二隻猴子、各兩顆桃子給其餘的三隻猴子。六天過後，四隻猴子分別擁有 13, 13, 13, 13 顆桃子，數量相等。

請撰寫一個程式計算，最少要幾天之後，才能使得所有的猴子都擁有等量的桃子。

输入格式

$$\begin{aligned} &T \\ &\text{testcase}_1 \\ &\text{testcase}_2 \\ &\vdots \\ &\text{testcase}_T \end{aligned}$$

• $T$ 表示測試資料個數。
• $\text{testcase}_i$ 為第 $i$ 筆測試資料。

每一筆測試資料的輸入格式如下

$$\begin{aligned} &n \ k \\ &a_1 \ a_2 \ \ldots \ a_n \end{aligned}$$

• $n$ 為猴子的數量。
• $k$ 為桃子每天的產量。
• $a_i$ 代表第 $i$ 隻猴子擁有的桃子數量。

输出格式

輸出 $T$ 筆測試資料之答案

$$\begin{aligned} &\text{answer}_1 \\ &\text{answer}_2 \\ &\vdots \\ &\text{answer}_T \end{aligned}$$

• $\text{answer}_i$ 為第 $i$ 筆測試資料之答案。

每一筆測試資料答案的輸出格式如下：如該組測試資料在 $x$ 天後，所有猴子能夠擁有等量的桃子，則輸出一個整數 $x$，如果那天永遠不可能到來，則輸出 poor monkeys。

5
4 7
1 2 3 4
4 4
1 2 3 4
8 3
1 1 2 3 4 5 6 9
8 4
1 1 2 3 4 5 6 9
2 1
0 1

6
poor monkeys
19
poor monkeys
1

提示

測資限制

• $1 \leq T \leq 5 \times 10^5$。
• $2 \leq n \leq 10^6$。
• $1 \leq k \leq 10^9$。
• $0 \leq a_i \leq 10^9$。
• $a_1 \leq a_2 \leq \dots \leq a_n$ 且 $a_1 < a_n$。
• 輸入的數皆為整數。
• $T$ 筆測試資料中 $n$ 的總和 $\sum n \leq 10^6$。

評分說明

本題共有五組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

子任務	分數	額外輸入限制
1	2	$\sum n \leq 100$，$k = 1$，$a_i \leq 100$ 且保證最少天數存在。
2	3	$\sum n \leq 100$，$k = n-1$，$a_i \leq 100$ 且保證最少天數存在。
3	29	$\sum n \leq 1000$，$k \leq 1000$，$a_i \leq 1000$ 且保證若最少天數存在，則不超過 $10^4$。
4	39	$\sum n \leq 10^5$，$k \leq 10^5$，$a_i \leq 10^5$，見註 2。
5	27	無額外限制。

• 註 1：「最少天數存在」的意思是有一天所有猴子可以擁有等量的桃子，不存在的意思則是這一天永遠不可能到來。
• 註 2：子任務 4 保證對於那些最少天數存在的測試資料，最少天數的總和不超過 $10^5$。換句話說，正確答案中輸出的數字總和不超過 $10^5$。