Public Judge

pjudge

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

[+1]

题目描述

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

输入格式

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

输出格式

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

样例一

input

1 8

output

样例二

input

5 84

output

数据范围与提示

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

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

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

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