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 write all the numbers from 1 to N to form a continuous string of digits. Next he replaced substrings of identical digits with a single digit. For example string fragment "14445556677666" would be changed to "145676". Then he asked his fellow professors: given a length of string S determine the number N which results in that kind of string S. Can you help the professors?

**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:13Output:12

### Explanation:

With N = 12, we get the string: 123456789101112.

Because there are three consecutive number ones, 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: | 1s |

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: | Ukraina OI |