Digits Sequence (Hard Edition)

1000ms

262144K

Description:

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.

Input:

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

Output:

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

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Informação

Provedor Codeforces

Código CF1177B