Это простая версия задачи. Отличие между версиями заключается в ограничении на $$$x$$$: в этой версии $$$x \le 10^5$$$.
У Поликарпа есть последовательность всех натуральных чисел от $$$1$$$ до $$$10^{12}$$$. Он решает модифицировать эту последовательность, для этого он $$$x$$$ раз выполнит следующее действие:
- Одновременно удалить все числа на позициях $$$y$$$, $$$2 \cdot y$$$, $$$3 \cdot y$$$, ... $$$m \cdot y \le n$$$, где $$$n$$$ — длина текущей последовательности.
После этого Поликарп хочет найти в оставшейся последовательности $$$k$$$-е число или определить, что длина результирующей последовательности меньше $$$k$$$.
Помогите Поликарпу справиться с данной задачей!
Рассмотрим пример. Пусть $$$x = 2$$$, $$$y = 3$$$, $$$k = 5$$$, тогда:
Числа, зачеркнутые красной линией, удалены после первой операции, а числа, зачеркнутые синей линией, удалены после второй операции. Тогда число на $$$k = 5$$$ позиции — число $$$10$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит три целых числа $$$x$$$, $$$y$$$, $$$k$$$ ($$$1 \le x \le \bf{10^{5}}$$$, $$$1 \le y, k \le 10^{12}$$$).
Для каждого набора входных данных выведите положительное целое число, которое стоит на $$$k$$$-й позиции в результирующей последовательности, или $$$-1$$$, если длина результирующей последовательности меньше $$$k$$$.
62 3 52 5 120 2 1000000000000175 10 28100000 998244353 19999999991 1 1
101-123390303042000199999-1
