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?

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.

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

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 $ after1 $ \{\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 $ .