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 ≤ 10000) — 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
import java.util.Scanner;

public class Digits_Sequence_Hard_Edition_Kamel {
	public static void main(String [] args) {
		Scanner sc = new Scanner(System.in);
		long k = sc.nextLong();
		getResult(k);
		sc.close();
	}
	
	static void getResult(long k) {
		long val = 0;;
		long ten = 1;
		int i = 1;
		while(true) {
			val = 9l*ten*i;
			if(k<=val) {
				decompose(k, ten, i);
				System.exit(0);
			}
			else {
				k-=val;
				ten = ten*10l;
				i++;
			}
		}
	}
	
	static void decompose(long offset, long ten, int size) {
		long val = ten - 1 +(long) Math.ceil((double)offset/size);
		int digit = (int)(((offset%size))-1 + size)%size;
		
		String result = String.valueOf(val).substring(digit, digit+1);
		System.out.print(result);
	}
}
