CF1177B Digits Sequence (Hard Edition)

Let's write all the positive integer numbers one after another from $ 1 $ without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536... Your task is to print the $ k $ -th digit of this sequence.

The first and only line contains integer $ k $ ( $ 1 \le k \le 10^{12} $ ) — the position to process ( $ 1 $ -based index).

Print the $ k $ -th digit of the resulting infinite sequence.