1238. K-th Smallest in Lexicographic Order

Given integers n and k, return the k-th smallest integer in the range [1, n] when the numbers are sorted in lexicographic (dictionary) order. The input is JSON {n, k}.

Input: JSON {n, k}.

Output: Integer — the k-th lexicographically smallest number.

Examples

Input: {"n":13,"k":2}
Output: 10
Explanation: Order: 1, 10, 11, 12, 13, 2, ...

Input: {"n":1,"k":1}
Output: 1
Explanation: Only one number.

Input: {"n":100,"k":10}
Output: 17
Explanation: The tenth in lexicographic order.

Constraints

• 1<=k<=n<=10^9

Asked by