30826번 - 그 긴 수

문제

팰린드롬 수는 앞에서 읽어도, 뒤에서 읽어도 같은 수를 말한다. 예를 들어, 7ドル,ドル 88ドル,ドル 14641ドル$은 팰린드롬 수지만 201ドル,ドル 329ドル,ドル 4700ドル$ 등은 팰린드롬 수가 아니다.

상윤이는 팰린드롬 수 중 양의 정수면서 첫 자리가 0ドル$이 아닌 팰린드롬 수들을 1ドル$부터 차례대로 이어 붙여 아주 긴 수를 새로 만들고 '그 긴 수'라 명명하였다. 하지만 '그 긴 수'가 너무 긴 나머지 상윤이는 '그 긴 수'의 앞에서 $k$번째 숫자가 몇인지 알아내는 데 어려움을 겪고 있다.

'그 긴 수'의 앞에서 30자리는 다음과 같다.

• 123456789112233445566778899101ドル \cdots $

상윤이의 궁금증을 해결해 주기 위해, 양의 정수 $k$가 주어질 때 '그 긴 수'의 앞에서 $k$번째 숫자를 구해 주자.

입력

첫 번째 줄에 양의 정수 $k$가 주어진다. (1ドル\leq k\leq 10^{16}$)

출력

'그 긴 수'의 앞에서 $k$번째 숫자를 출력한다.

제한

힌트