For a positive integer $k$, a "poisonous pseudo-strong number" $x$ is defined as a positive integer such that the decimal representation of $x \times (10^k - 1)$ does not contain the digit $9$. You need to find the $n$-th poisonous pseudo-strong number.
Input
A single line containing two integers $k$ and $n$.
Output
A single line containing the $n$-th poisonous pseudo-strong number.
Examples
Input 1
1 8
Output 1
9
Input 2
5 84
Output 2
11235
Constraints
| Subtask ID | $k \leq$ | $n \leq$ | Score |
|---|---|---|---|
| $1$ | $3$ | $1000$ | $25$ |
| $2$ | $1$ | $10^{18}$ | $35$ |
| $3$ | $18$ | $10^{18}$ | $40$ |
For all test cases, $1 \leq k \leq 18$ and $1 \leq n \leq 10^{18}$.