CF1852A.Ntarsis' Set

Ntarsis has been given a set $S$, initially containing integers $1, 2, 3, \ldots, 10^{1000}$ in sorted order. Every day, he will remove the $a_1$-th, $a_2$-th, $\ldots$, $a_n$-th smallest numbers in $S$ simultaneously.

What is the smallest element in $S$ after $k$ days?

Ntarsis 得到了一个集合 $S$，初始时按升序包含整数 $1, 2, 3, \ldots, 10^{1000}$。每天，他将同时删除 $S$ 中第 $a_1$ 小、第 $a_2$ 小、……、第 $a_n$ 小的数。

经过 $k$ 天后，$S$ 中最小的元素是多少？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case consists of two integers $n$ and $k$ ($1 \leq n,k \leq 2 \cdot 10^5$) — the length of $a$ and the number of days.

The following line of each test case consists of $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the elements of array $a$.

It is guaranteed that:

• The sum of $n$ over all test cases won't exceed $2 \cdot 10^5$;
• The sum of $k$ over all test cases won't exceed $2 \cdot 10^5$;
• $a_1 \lt a_2 \lt \cdots \lt a_n$ for all test cases.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n,k \leq 2 \cdot 10^5$）——分别表示数组 $a$ 的长度和天数。

每个测试用例的下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）——即数组 $a$ 的元素。

保证满足以下条件：

• 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$；
• 所有测试用例中 $k$ 的总和不超过 $2 \cdot 10^5$；
• 对所有测试用例，均有 $a_1 \lt a_2 \lt \cdots \lt a_n$。

For each test case, print an integer that is the smallest element in $S$ after $k$ days.

对于每个测试用例，输出一个整数，表示经过 $k$ 天后集合 $S$ 中的最小元素。

For the first test case, each day the $1$-st, $2$-nd, $4$-th, $5$-th, and $6$-th smallest elements need to be removed from $S$. So after the first day, $S$ will become \require{cancel} ${\cancel 1, \cancel 2, 3, \cancel 4, \cancel 5, \cancel 6, 7, 8, 9, \ldots} = {3, 7, 8, 9, \ldots}$. The smallest element is $3$.

For the second case, each day the $1$-st, $3$-rd, $5$-th, $6$-th and $7$-th smallest elements need to be removed from $S$. $S$ will be changed as follows:

Day

$S$ before

$S$ after

1

${\cancel 1, 2, \cancel 3, 4, \cancel 5, \cancel 6, \cancel 7, 8, 9, 10, \ldots }$

$\to$

${2, 4, 8, 9, 10, \ldots}$

2

${\cancel 2, 4, \cancel 8, 9, \cancel{10}, \cancel{11}, \cancel{12}, 13, 14, 15, \ldots}$

$\to$

${4, 9, 13, 14, 15, \ldots}$

3

${\cancel 4, 9, \cancel{13}, 14, \cancel{15}, \cancel{16}, \cancel{17}, 18, 19, 20, \ldots}$

$\to$

${9, 14, 18, 19, 20, \ldots}$

The smallest element left after $k = 3$ days is $9$.

对于第一个测试用例，每天需要从集合 $S$ 中移除第 $1$ 小、第 $2$ 小、第 $4$ 小、第 $5$ 小和第 $6$ 小的元素。因此，第一天之后，$S$ 将变为 \require{cancel} ${\cancel 1, \cancel 2, 3, \cancel 4, \cancel 5, \cancel 6, 7, 8, 9, \ldots} = {3, 7, 8, 9, \ldots}$。此时最小的元素为 $3$。

对于第二个测试用例，每天需要从集合 $S$ 中移除第 $1$ 小、第 $3$ 小、第 $5$ 小、第 $6$ 小和第 $7$ 小的元素。$S$ 的变化过程如下：

天数	变化前的 $S$	变化后的 $S$
1	${\cancel 1, 2, \cancel 3, 4, \cancel 5, \cancel 6, \cancel 7, 8, 9, 10, \ldots }$	$\to$
2	${\cancel 2, 4, \cancel 8, 9, \cancel{10}, \cancel{11}, \cancel{12}, 13, 14, 15, \ldots}$	$\to$
3	${\cancel 4, 9, \cancel{13}, 14, \cancel{15}, \cancel{16}, \cancel{17}, 18, 19, 20, \ldots}$	$\to$

经过 $k = 3$ 天后，剩余元素中最小的值为 $9$。