题目描述

有一个集合 $S$，初始时包含所有正整数（即 $S = \{1, 2, 3, \dots\}$）。

接下来进行 $k$ 天操作。每一天，你同时从 $S$ 中删除当前第 $a_1$ 小、第 $a_2$ 小、$\dots$、第 $a_n$ 小的数。删除操作同时进行，指定了相同位置的多次删除仅生效一次。

求 $k$ 天后，$S$ 中最小的数是多少。

输入格式

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n, k$，表示每次操作指定删除位置的个数与操作天数。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，含义见题目描述。保证 $a_i$ 严格递增。

输出格式

对于每组数据，输出一行一个整数，表示 $k$ 天后 $S$ 中最小的数。

样例

2
5 3
1 3 5 6 7
10 150000
1 3 4 5 10 11 12 13 14 15

9
1499986

1
2 3
1 3

6

样例解释

对于第一组样例的第一组数据（$n=5, k=3, a=[1,3,5,6,7]$）：

• 初始 $S = \{1,2,3,4,5,6,7,8,9,10,\dots\}$
• 第一天：删除第 $1,3,5,6,7$ 小的数，即删除 $1,3,5,6,7$，$S = \{2,4,8,9,10,\dots\}$
• 第二天：删除第 $1,3,5,6,7$ 小，即删除 $2,8,10,11,12$，$S = \{4,9,13,14,15,\dots\}$
• 第三天：删除第 $1,3,5,6,7$ 小，即删除 $4,13,17,18,19$，$S = \{9,14,18,19,20,\dots\}$
• $S$ 中最小的数为 $9$。

对于第一组样例的第二组数据（$n=10, k=150000$），答案为 $1499986$。

对于第二组样例（$n=2, k=3, a=[1,3]$）：

• 第一天：删除第 $1,3$ 小的数，即删除 $1,3$，$S = \{2,4,5,6,\dots\}$
• 第二天：删除第 $1,3$ 小的数，即删除 $2,5$，$S = \{4,6,7,8,\dots\}$
• 第三天：删除第 $1,3$ 小的数，即删除 $4,7$，$S = \{6,8,9,10,\dots\}$
• 最小数为 $6$。

数据范围与约定

对于所有数据，满足 $1 \le T \le 10^5$，$1 \le n \le 2 \times 10^5$，$1 \le k \le 10^9$，$1 \le a_i \le 10^9$，$a_i$ 严格递增。保证一个测试点内所有数据的 $n$ 之和不超过 $2 \times 10^5$。

下发样例

下发样例下载