Поздним осенним вечером n роботов собрались в весёлой дружеской компании. У каждого робота есть свой уникальный идентификатор — целое число от 1 до 109.
В какой-то момент роботы решили поиграть в игру «Снежный ком». Правила игры следующие: сначала все роботы становятся в ряд, затем первый робот произносит свой идентификатор. После этого второй робот произносит идентификатор первого робота, а затем произносит свой идентификатор. Затем третий робот произносит идентификатор первого робота, затем второго робота, а затем свой. Этот процесс продолжается слева направо до тех пор, пока n-й робот не произнесёт свой идентификатор.
Перед вами стоит задача — определить идентификатор, который будет назван k-м по счёту.
Выходные данные
Выведите идентификатор робота, который будет произнесён k-м по счёту (используется нумерация с единицы).
Примечание
В первом тестовом примере идентификаторы роботов будут произнесены в следующем порядке: 1, 1, 2. Так как k = 2, ответ равен 1.
Во втором тестовом примере идентификаторы роботов будут произнесены в следующем порядке: 10, 10, 4, 10, 4, 18, 10, 4, 18, 3. Так как k = 5, ответ равен 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
1 2
|
1
|
|
2
|
4 5
10 4 18 3
|
4
|