PKL out of her flop era


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

PKL is a girl with a huge passion for music. She has entered countless competitions and released lots of tracks. A few of them went viral, but the rest were total FLOPs. Even so, she kept chasing her dream. She has worked all sorts of jobs to earn money for her records, from herding cows (and getting chased by them), to selling scented candles online, and most recently, she switched to assembling cameras. On those FLOP days, she always felt down, so she decided to write consecutive integers in a scratch notebook, waiting for the day she would escape her FLOP fate.

She started writing from 1, then 2, ... one after another. Ten years went by like this, and after going villain mode with a wig made of real blonde hair, she finally escaped her FLOP era by filming videos of herself bothering people all over TikTok.

Today is the day she stops writing numbers, and she notices that the string of numbers she has written is very long. To honor the days of eating bánh tráng trộn, she starts counting the digits in this string. She counts \(N\) digits.

Determine the last number PKL wrote, given that the string has a length of \(N\) digits.

Input

  • A single line containing a positive integer \(N \ (1\le N \le 10^{15})\).

It is guaranteed that a valid answer always exists.

Output

  • A single integer, the answer to the problem.

Scoring

  • Subtask 1 (60%): \(N \le 10^5\).
  • Subtask 2 (10%): \(N \le 10^8\).
  • Subtask 3 (30%): No additional constraints.

Examples

Example 1

input

6

output

6
Example 2

input

15

output

12

Explanation

The string PKL wrote in Example 2 is 123456789101112.


Comments

There are no comments at the moment.