#D3115. Digits Sequence (Hard Edition)
Digits Sequence (Hard Edition)
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.
Input
The first and only line contains integer k (1 ≤ k ≤ 10^{12}) — the position to process (1-based index).
Output
Print the k-th digit of the resulting infinite sequence.
Examples
Input
7
Output
7
Input
21
Output
5
inputFormat
Input
The first and only line contains integer k (1 ≤ k ≤ 10^{12}) — the position to process (1-based index).
outputFormat
Output
Print the k-th digit of the resulting infinite sequence.
Examples
Input
7
Output
7
Input
21
Output
5
样例
21
5