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.


-----Examples-----
Input
7

Output
7

Input
21

Output
5

Difficulty: interview

Starter code:

Solutions:
k = int(input())

if k<=9:
    print(k)
else:
    num_arr = [9*(i+1)* 10**i for i in range(11)]

    index = 0

    while True:
        if k<=num_arr[index]:
            break
        else:
            k -= num_arr[index]
            index += 1

    digit = index+1
    k += digit-1


    num = k//digit
    offset = k%digit

    string_num = str(10**(digit-1)+ num-1)

    print(string_num[offset])



def f(x): #including x
	dig, cnt = 1, 9
	ans = 0
	while dig != len(str(x)):
		ans += dig * cnt
		dig += 1
		cnt *= 10
	ans += (x - (cnt // 9) + 1) * dig
	return ans
k = int(input())
l, r = 1, 1000000000000
if k == 1:
    print(1)
    return
while l < r:
	mid = (l + r + 1) >> 1
	if f(mid) < k:
		l = mid
	else:
		r = mid - 1
k -= f(l)
l += 1
print(str(l)[k - 1])

import math
n=int(input())
# 99-9
# 999-99
a=[9]
for i in range(2,20):
    a.append(10**i   - 10**(i-1) )
b=[0]
for i in range(1,20):
    b.append(b[-1]+ i*a[i-1])
for i in range(20):
    if n<=b[i]:
        break
p=b[i-1]
k=n-p
# print(p,k)
ans=10**(i-1) - 1 + math.ceil(k/(i))
# print(k,p,i)
# print(ans,i,k)
if k%i==0:
    print(('0'+str(ans))[i])
else:
    print(('0'+str(ans))[k%i])

k = int(input())
ch = 0
i = 0
r = 1
while k > r - 1:
    r += 9 * (i + 1) * 10 ** i
    i += 1
r -= 9 * i * 10 ** (i - 1)
#print(r, i)
print(str((k - r) // i + 10 ** (i - 1))[(k - r) % i]  )


k=int(input())
i=0
r=1
while(k>=r):
    r+=9*(i+1)*10**i
    i+=1
r=r-(9*i*10**(i-1))
ans=str(((k-r)//i)+10**(i-1))[(k-r)%i]
print(ans)

k = int(input())
prev=0
nextt=0
NumofDigits=0
#i = 0
#while(summ<(2^12)):
while(True):
    prev = nextt
    nextt = nextt+(9*(10**(NumofDigits-1))*NumofDigits)
    if(k>= prev and k<=nextt):
        break
    NumofDigits=NumofDigits+1
if(NumofDigits==1):
    print(k)
else:
    result = (10**(NumofDigits-1))+int((k-(prev+1))/NumofDigits)
    i=0
    while(True):
        if (k-int(prev+1))%NumofDigits == i:
            break
        i=i+1
    result = str(result)
    print(result[i])

a = int(input())
c = [1] * 30
for i in range (1,20):
	c[i] = 9 * i * pow(10,i-1)
for i in range (1,15):
	if (a > c[i]):
		a -= c[i]
	else:
		d = int((a-1) / i + pow(10,i-1) - 1)
		e = (a-1) % i + 1
		f = str(d+1)
		print(f[e-1])
		return

k = int(input()) - 1

l = 1
c = 9
while k >= c*l:
    k -= c * l
    l += 1
    c *= 10

c = 10**(l-1) + k // l
print(str(c)[k % l])


def mp():
    return map(int, input().split())

def f(i):
    return (10 ** i - 10 ** (i - 1)) * i

n = int(input())

i = 1
sum = 0
while n - f(i) >= 0:
    n -= f(i)
    sum += f(i) // i
    i += 1

print(str(sum + (n + i - 1) // i)[n % i - 1])

#!/usr/bin/env python3
from sys import stdin


def solve(tc):
    k = int(stdin.readline().strip())
    cmp = 9
    ndigit = 1

    while k>(cmp*ndigit):
        k -= cmp*ndigit
        cmp *= 10
        ndigit += 1
    
    num = (10**(ndigit-1)) + ((k-1) // ndigit)
    pos = (k-1) % ndigit

    print(str(num)[pos])
    pass


LOCAL_TEST = not __debug__
if LOCAL_TEST:
    infile = __file__.split('.')[0] + "-test.in"
    stdin = open(infile, 'r')

tcs = (int(stdin.readline().strip()) if LOCAL_TEST else 1)
tc = 1
while tc <= tcs:
    solve(tc)
    tc += 1

import sys
k=int(input())
if type(k)!=int or k<=0 or k>pow(10,12) :
        print("wrong input. try again")
        return
lim_init=lim=decimal=9
c=0
while True:
        c+=1
        if k<=lim:
                diff=lim-k #189-21
                pos=diff%c
                diff=int(diff/c) #168/2=84
                diff=decimal-diff #99-84
                print(''.join(list(reversed(str(diff))))[pos])
                break
        else:
                decimal = int(str(lim_init)*(c+1))
                lim+=int(str(lim_init)+'0'*c)*(c+1)




n=int(input())

x=1

while n>(10**(len(str(x))-1)*9*len(str(x))):
    n-=10**(len(str(x))-1)*9*len(str(x))

    x*=10
    
t=len(str(x))
nadighe=False
while nadighe==False:
    qw=1
    nadighe=True
    while n>(10**(len(str(qw))-1)*9*t):
        n-=10**(len(str(qw))-1)*9*t
        nadighe=False
        qw*=10
    x+=qw-1
   
    
while n>len(str(x)):
    n-=len(str(x))
    x+=1
for i in range(len(str(x))):
    if n!=0:
        s=str(x)[i]
        n-=1
print(s)
    


n = int(input())
limit_int = limit = decimal = 9
count = 0
while True:
    count += 1
    if n <= limit:
        difference = limit - n
        position = difference % count
        difference = difference // count
        difference = decimal - difference
        print(''.join(list(reversed(str(difference))))[position])
        break
    else:
        decimal = int(str(limit_int) * (count + 1))
        limit += int(str(limit_int) + '0' * count) * (count + 1)


"""
Strategy: Split sequence into subsequences
according to number of digits. Then find corresponding
number and digit in that number.
"""

# Standard input.
k=int(input())

# Initilize sequence
num_digits=1
num_numbers=9

k-=1
while k>num_digits*num_numbers:
    # Move sequence starting point. 
    k -= num_numbers*num_digits
    num_digits += 1
    num_numbers *= 10

# Generate number.
number = 10**(num_digits - 1) + k // num_digits
# Find index in that number
index = k % num_digits
answer = str(number)[index]
print(answer)

L = [(i+1)*9*10**i for i in range(12)]
number = int(input())

exponent=0
while number >= 0:
    number-=L[exponent]
    exponent+=1
exponent-=1
number%=L[exponent]
start = 10**exponent
numDigits = exponent+1
final = start+(number//numDigits-1)
remainder = number%numDigits
if remainder == 0:
    final = str(final)
    print(final[-1])
else:
    final = str(final+1)
    print(final[remainder-1])
'''print(number, exponent, numDigits, start, final, remainder)'''


T = (0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889, 8888888889, 98888888889, 1088888888889)
k = int(input())
a = 0
for i in T:
    if i - k > 0:
        a = T.index(i)
        break
temp = T[a] - k
x = temp % a
res = (10 ** a) - 1 - int(temp / a)
ans = int((res % (10 ** (x+1))) / (10 ** x))
print(ans)


k=int(input())
x=0
c=0
while(x<k):
    x+=9*(10**c)*(c+1)
    c+=1
p=(x-k)%c
k=((10**c)-int(((x-k)/c))-1)
k=str(k)
print(k[len(k)-(p)-1])

k=int(input())
a=[]
for i in range(0,12):
    s=9*pow(10,i)*(i+1)
    if k<=s:
        break
    else:
        k-=s
pos=i+1
num=(pow(10,pos-1)+(k//pos)-1)
if k%pos==0:
    print(str(num)[-1])
else:
    print(str(num+(0 if pos==1 else 1))[(k%pos)-1])
 


index = int(input())

total = 9
n = 1

while index > total:
    total += (n + 1) * (10**n) * 9
    n += 1
last = 10**(n - 1)
total -= n * 9 * last
index = index - total


r = index % (n)
k = index // n

number = last + k


if r == 0:
    print(str(number - 1)[n-1])
else:
    print(str(number)[r - 1])


l = []
n = []
sum = 0
multiply = 9
for i in range(1,12):
    s = '9' * i
    n.append(int(s))
    sum+=i*multiply
    multiply *= 10
    l.append(sum)
k = int(input())
if(k<9):
    print(k)
else:
    t = 0
    for i in range(len(l)):
        if(k < l[i]):
            t=i
            break
    temp = k-l[t-1]
    offset = temp%(t+1)
    value = temp//(t+1)
    number = n[t-1]+value
    if(offset == 0):
        print(number%10)
    else:
        number += 1
        offset -= 1
        print(str(number)[offset])

k=int(input())
i=0
r=1
while(k>=r):
    r+=9*(i+1)*10**i
    i+=1
r=r-(9*i*10**(i-1))
ans=str(((k-r)//i)+10**(i-1))[(k-r)%i]
print(ans)


k = int(input())
n = 1

for i in range(1, 20):
    if k < n + 9 * 10 ** (i - 1) * i:
        print(str(10 ** (i - 1) + (k - n) // i)[(k - n) % i] )
        break
    n += 9 * 10 ** (i - 1) * i



a= int(input())
i=1
amount=a
while amount>i*((10**i)-(10**(i-1))):
    amount =amount - i*((10**i)-(10**(i-1)))
    i=i+1  
x= amount//i
y=amount%i
# print(amount)
# print(i)
# print(x)
# print(y)
if y==0: 
    if i==1:
        print(x%10)
    else:
        print((10**(i-1) + x -1)%10)
else:
    if i==1:
        print(x%10)
    else:
        print(((10**(i-1) + x)//(10**(i-y)))%10)

#import sys
#digit = int(sys.argv[1])
digit = int(input())

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

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]}")


def get_kth_digit(i):
    if i < 10:
        return i

    batch = 9
    count = 9
    width = 1

    while i >  10 * batch * (width + 1) + count:
        batch *= 10
        width += 1
        count += batch * width

    
    k = i - count - 1
    num = 10 ** width + k// (width + 1)
    return str(num)[k % (width + 1)]

def main():
    i = int(input())

    print(get_kth_digit(i))

def __starting_point():
    main()
__starting_point()