Пин сконструировал супер-приёмник, который ловит сигналы от всех цивилизаций в нашей Галактике.
Лосяш выяснил, что цивилизации живут упорядоченно: их радиочастоты соответствуют простым числам.
Крош решил, что ему срочно нужно поделиться рецептом морковного пирога с K-ой по счёту цивилизацией в секторе
частот от от A до B. Пин предупреждает: «О майн Готт, Крош! Если ты ошибёшься хоть на один герц, мы поймаем помехи от чёрной дыры!»
Помоги Крошу вычислить точную частоту для связи. Если в указанном секторе [A;B] живёт меньше, чем K цивилизаций,
значит, Крош сегодня ни до кого не дозвонится (выводи -1)
Входные данные:
три числа \(A, B, K (1 \le A < B \le 10^9, K \le10^6)\) |
Выходные данные:
Одно число - значение K-го простого числа |
Пример
| Входные данные |
Ожидаемый результат |
| 1 10 3 |
5 |
| 10 20 10 |
-1 |
|
Нюша
не гарантирует выполнение программы, реализованной на языке C++,
но знает, что её можно решить на Python