题目描述

数字研究员 Nina 喜欢避开数字 $9$。她写下一个由 $k$ 个数字 $9$ 组成的数：

$$\underbrace{999\ldots 9}_{k\text{ 个 }9}.$$

现在她按正整数 $x$ 从小到大的顺序检查。若

$$x\cdot \underbrace{999\ldots 9}_{k\text{ 个 }9}$$

的十进制表示中不含数字 $9$，则称 $x$ 是合法的。

给定 $k$ 和 $n$，请找出第 $n$ 个合法正整数 $x$。

输入格式

输入一行包含两个整数 $k,n$。

输出格式

输出一个整数，表示第 $n$ 个合法正整数 $x$。

数据范围

• $1\le k\le 18$；
• $1\le n\le 10^{18}$。

样例 1

输入

1 1

输出

2

样例 2

输入

1 8

输出

9

样例 3

输入

1 9

输出

12

样例 4

输入

1 10

输出

13

样例 5

输入

5 1

输出

11112

样例 6

输入

5 84

输出

11235

样例 7

输入

5 668

输出

12345

样例 8

输入

5 733942

输出

2281488

样例说明

当 $k=1$ 时，所有合法数从小到大依次以

$$2,3,4,5,6,7,8,9,12,13,\ldots$$

开头。