B. Последовательность цифр (усложнённая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Выпишем подряд без каких-либо разделителей все целые числа от $$$1$$$ и далее (то есть выпишем в одну строку). В результате получится последовательность цифр, которая начинается вот так: 123456789101112131415161718192021222324252627282930313233343536...

Ваша задача вывести $$$k$$$-ю цифру в этой последовательности.

Входные данные

В первой и единственной строке записано целое $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — индекс цифры (индексы нумеруются от $$$1$$$).

Выходные данные

Выведите $$$k$$$-ю цифру построенной бесконечной последовательности цифр.

Примеры
Входные данные
7
Выходные данные
7
Входные данные
21
Выходные данные
5