Sort

Fox Jiro and Eel Saburo are good friends. Saburo uses a strange way to compare integers. Please help Jiro understand it.

For a positive integer n, let d(n) be the sum of its digits in base 10. For example, d(407) = 4+0+7 = 11.

When comparing two different integers x and y, Saburo first compares their sums of digits, i.e., the values d(x) and d(y). If they differ, the one with the smaller sum is smaller. For example, for Saburo 50 is smaller than 16, because d(50) < d(16).

If the numbers have the same sum of digits, Saburo compares them lexicographically (i.e., as strings). For example, for Saburo the number 111 is smaller than the number 3, because d(111) = d(3) and "111" < "3". Also, the number 470 is smaller than 4700, because "470" < "4700".

Let A be the sequence of integers {0, 1, ..., 999999999999999998, 999999999999999999 (10^18 - 1)}. Let B be the sequence A, ordered according to Saburo's rules. You are given a long idx, representing a 1-based index into B. Return the corresponding element of B.