1177_B. 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
```python
#import sys
#digit = int(sys.argv[1])
digit = int(input())

if int(digit) <= 9:
    print(digit)
    exit()

start_range = 1
end_range = 9

power = 1
digit_count = 2
while not (start_range <= digit and digit <= end_range):
    start_range = end_range + 1
    end_range = 9 * 10**power * digit_count + start_range - 1
    power += 1
    digit_count += 1

offset_number = (digit - start_range) // (digit_count - 1)
#print(f"{digit} - {start_range} mod {digit_count-1} = {offset_number}")
number = str(10**(power - 1) + offset_number)
#print(f"10^ {power - 1} + {offset_number} = {number}")
offset_digit = (digit - start_range) % (digit_count - 1) 
#print(f"{digit} - {start_range} mod {digit_count - 1 } = {offset_digit}")
#print(f"{number} {number[-offset_digit]}")
print(f"{number[offset_digit]}")

```