Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |

## LQDNUMS - LQDNUMBERS |

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 ≤ 10^{18 })

### 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 |