Sleep Disorder

Interview

Time limit1sMemory limit128 MB

Summary

Concatenate the natural numbers 1, 2, 3, ... into one digit string and return the digit at position N.

Level: Medium4 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Kangmin has a sleep disorder and suffers quite a bit from not being able to fall asleep. Whenever sleep does not come he counts sheep in his head, but tonight he counted a million of them and was still awake.

Having had enough, Kangmin decided to count in a new way. Writing the natural numbers from 1 onward one after another produces this string of digits:

$123456789101112\ldots$

Kangmin read that string one digit at a time. He did fall asleep, and the next morning he woke up and happily shouted "I read all the way to digit $N$ !"

Which digit sits at position $N$ of the string?

Input

The first line contains $N$ . $(1 \le N \le 100\,000\,000)$

Output

Print the single digit at position $N$ of the string. It is one of 0 through 9.

Examples2

Example 1
Input
```
15
```
Expected output
```
2
```
Example 2
Input
```
1
```
Expected output
```
1
```