A. Набор Ntarsis
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ntarsis получил набор $$$S$$$, изначально содержащий целые числа $$$1, 2, 3, \ldots, 10^{1000}$$$ в отсортированном порядке. Каждый день он будет одновременно удалять $$$a_1$$$-е, $$$a_2$$$-е, $$$\ldots$$$, $$$a_n$$$-е наименьшие числа в $$$S$$$.

Какое наименьшее число останется в $$$S$$$ после $$$k$$$ дней?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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 < a_2 < \cdots < a_n$$$ для всех наборов входных данных.
Выходные данные

Для каждого набора входных данных выведите целое число, которое является наименьшим элементом в $$$S$$$ после $$$k$$$ дней.

Пример
Входные данные
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
Примечание

В первом наборе входных данных каждый день удаляется $$$1$$$-й, $$$2$$$-й, $$$4$$$-й, $$$5$$$-й и $$$6$$$-й наименьшие элементы из $$$S$$$. Таким образом, после первого дня $$$S$$$ станет равным $$$\require{cancel}$$$ $$$\{\cancel 1, \cancel 2, 3, \cancel 4, \cancel 5, \cancel 6, 7, 8, 9, \ldots\} = \{3, 7, 8, 9, \ldots\}$$$. Наименьшим элементом является $$$3$$$.

Во втором наборе каждый день удаляется $$$1$$$-й, $$$3$$$-й, $$$5$$$-й, $$$6$$$-й и $$$7$$$-й наименьшие элементы из $$$S$$$. $$$S$$$ будет изменяться следующим образом:

День$$$S$$$ до$$$S$$$ после
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\}$$$

Наименьшим элементом, оставшимся после $$$k = 3$$$ дней, является $$$9$$$.