310570: CF1853C. Ntarsis' Set

C. Ntarsis' Settime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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 < a_2 < \cdots < a_n$ for all test cases.

Output

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

ExampleInput

7
5 1
1 2 4 5 6
5 3
1 3 5 6 7
4 1000
2 3 4 5
9 1434
1 4 7 9 12 15 17 18 20
10 4
1 3 5 7 9 11 13 15 17 19
10 6
1 4 7 10 13 16 19 22 25 28
10 150000
1 3 4 5 10 11 12 13 14 15

Output

3
9
1
12874
16
18
1499986

Note

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$.

题目大意：
Ntarsis有一个初始集合S，包含从1到$10^{1000}$的整数，并且已经按照从小到大的顺序排列。每天，他会同时移除集合S中第$a_1$、$a_2$、...、$a_n$小的元素。问经过k天后，集合S中最小的元素是什么？

输入输出数据格式：
输入：
- 第一行包含一个整数$t$（$1 \le t \le 10^5$），表示测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含两个整数$n$和$k$（$1 \le n, k \le 2 \cdot 10^5$），分别表示数组$a$的长度和天数。
- 第二行包含$n$个整数$a_1, a_2, ..., a_n$（$1 \le a_i \le 10^9$），表示数组$a$的元素。
- 保证所有测试用例中$n$的总和不超过$2 \cdot 10^5$，$k$的总和不超过$2 \cdot 10^5$，且对于所有测试用例，有$a_1 < a_2 < ... < a_n$。

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

示例：
```
输入：
7
5 1
1 2 4 5 6
5 3
1 3 5 6 7
4 1000
2 3 4 5
9 1434
1 4 7 9 12 15 17 18 20
10 4
1 3 5 7 9 11 13 15 17 19
10 6
1 4 7 10 13 16 19 22 25 28
10 150000
1 3 4 5 10 11 12 13 14 15

输出：
3
9
1
12874
16
18
1499986
```

注意：
- 对于第一个测试用例，每天需要从S中移除第1、2、4、5、6小的元素。所以经过1天后，S将变为$\{3, 7, 8, 9, ...\}$。最小的元素是3。
- 对于第二个测试用例，每天需要从S中移除第1、3、5、6、7小的元素。S将按以下方式改变：
- 第1天：$\{2, 4, 8, 9, 10, ...\}$
- 第2天：$\{4, 9, 13, 14, 15, ...\}$
- 第3天：$\{9, 14, 18, 19, 20, ...\}$
经过3天后剩下的最小元素是9。题目大意： Ntarsis有一个初始集合S，包含从1到$10^{1000}$的整数，并且已经按照从小到大的顺序排列。每天，他会同时移除集合S中第$a_1$、$a_2$、...、$a_n$小的元素。问经过k天后，集合S中最小的元素是什么？ 输入输出数据格式： 输入： - 第一行包含一个整数$t$（$1 \le t \le 10^5$），表示测试用例的数量。 - 每个测试用例包含三行： - 第一行包含两个整数$n$和$k$（$1 \le n, k \le 2 \cdot 10^5$），分别表示数组$a$的长度和天数。 - 第二行包含$n$个整数$a_1, a_2, ..., a_n$（$1 \le a_i \le 10^9$），表示数组$a$的元素。 - 保证所有测试用例中$n$的总和不超过$2 \cdot 10^5$，$k$的总和不超过$2 \cdot 10^5$，且对于所有测试用例，有$a_1 < a_2 < ... < a_n$。 输出： - 对于每个测试用例，输出一行，包含一个整数，表示经过k天后集合S中的最小元素。 示例： ``` 输入： 7 5 1 1 2 4 5 6 5 3 1 3 5 6 7 4 1000 2 3 4 5 9 1434 1 4 7 9 12 15 17 18 20 10 4 1 3 5 7 9 11 13 15 17 19 10 6 1 4 7 10 13 16 19 22 25 28 10 150000 1 3 4 5 10 11 12 13 14 15 输出： 3 9 1 12874 16 18 1499986 ``` 注意： - 对于第一个测试用例，每天需要从S中移除第1、2、4、5、6小的元素。所以经过1天后，S将变为$\{3, 7, 8, 9, ...\}$。最小的元素是3。 - 对于第二个测试用例，每天需要从S中移除第1、3、5、6、7小的元素。S将按以下方式改变： - 第1天：$\{2, 4, 8, 9, 10, ...\}$ - 第2天：$\{4, 9, 13, 14, 15, ...\}$ - 第3天：$\{9, 14, 18, 19, 20, ...\}$ 经过3天后剩下的最小元素是9。