LQDNUMS - LQDNUMBERS


He choose a number N ( 1 ≤ N ≤ 10^18 ), 

then wrote all the numbers from 1 to N to form a continuous string of digits. Next he replaced substrings of indentical digits with a single digit. For example string fragment "14445556677666" would be changed to "145676". He named this shortened string S. Then he specified a problem for his fellow professors: given a length of string S determine the number N witch results in that kind of string S. The task has proven to be too much for Mathematicans. can you solve it? 

During a meeting with professors in the Asian Confederation of Mathematics, a Russian professor came up with a problem: 

He choose a number N ( 1 ≤ N ≤ 10^18 ), then wrote all the numbers from 1 to N to form a continuous string of digits. Next he replaced substrings of indentical digits with a single digit. For example string fragment "14445556677666" would be changed to "145676". Then he specified a problem for his fellow professors: given a length of string S determine the number N witch results in that kind of string S. The task has proven to be too much for Mathematicans. can you solve it? 

Your task:

Write a program to help your country's mathematicians. 

Input

A single number M, length of the string S  ( 1 ≤ M ≤ 1018 )

Output

A single number N, the number which Russian professor selected. 

Example

Input:

13

Output:

12

Explaination:

With N = 12, we get the string:
- 123456789101112
Because three consecutive number one in the same location adjacent to the end, we delete the first two numbers, then we have
- 1234567891012
The length of this string is 13

Được gửi lên bởi:Tmbao
Ngày:2011-05-29
Thời gian chạy:3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Ukrana OI

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.