Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Hackable ✓
统计

题目描述

对于正整数 $k$,定义魔法数 $x$ 满足 $x\times(10^k-1)$ 的十进制表示不包含 $9$ 的正整数,你需要求出第 $n$ 个魔法数。

输入格式

一行两个整数 $k, n$。

输出格式

一行一个整数表示第 $n$ 个魔法数。

样例一

input

1 8

output

9

样例二

input

5 84

output

11235

数据范围与提示

测试点编号 $k$ $n\leq$
$1\sim 2$ $\leq 3$ $1000$
$3\sim 6$ $\leq 4$ $10^{18}$
$7\sim 10$ $\gt 4$

对于所有数据,$1\leq k\leq {18}$,$1\leq n\leq 10^{18}$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$