Ntarsis получил набор \(S\), изначально содержащий целые числа \(1, 2, 3, \ldots, 10^{1000}\) в отсортированном порядке. Каждый день он будет одновременно удалять \(a_1\)-е, \(a_2\)-е, \(\ldots\), \(a_n\)-е наименьшие числа в \(S\).
Какое наименьшее число останется в \(S\) после \(k\) дней?
Выходные данные
Для каждого набора входных данных выведите целое число, которое является наименьшим элементом в \(S\) после \(k\) дней.
Примечание
В первом наборе входных данных каждый день удаляется \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|