Problem G: 第p位

Problem G: 第p位

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 138  Solved: 45
[Status] [Submit] [Creator:]

Description

将所有正整数从小到大拼接在一起，能够组成一个无穷的数字字符串 S = 123456789101112131415161718192021……

求数字字符串 S 的第 p 个位置上的数字。

Input

一个整数 p（1 ≤ p ≤ 1012）。

Output

输出一个整数，表示数字字符串 S 第 p 个位置上的数字。

Sample Input Copy 

【样例输入1】
25
【样例输出1】
7
【样例输入2】
1000
【样例输出2】
3

HINT

数据规模与约定：
· 对于 30% 的数据，p ≤ 104
· 对于 60% 的数据，p ≤ 108
· 对于 100% 的数据，1 ≤ p ≤ 1012

[Submit][Status]