LQDNUMS - LQDNUMBERS

Giới hạn
  • Thời gian: 3.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ


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

  • Người up: coder_1340
  • Nguồn bài: Ukrana OI