B. Digits Sequence (Hard Edition)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet'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.InputThe first and only line contains integer k (1 \le k \le 10^{12}) — the position to process (1-based index).OutputPrint the k-th digit of the resulting infinite sequence.ExamplesInput
7
Output
7
Input
21
Output
5

7

7 
['binary search', 'divide and conquer', 'implementation', '*1800']