#P15721. 没有九的乘积

没有九的乘积

题目描述

数字研究员 Nina 喜欢避开数字 99。她写下一个由 kk 个数字 99 组成的数:

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

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

x⋅999…9⏟k 个 9x\cdot \underbrace{999\ldots 9}_{k\text{ 个 }9}

的十进制表示中不含数字 99,则称 xx 是合法的。

给定 kk 和 nn,请找出第 nn 个合法正整数 xx。

输入格式

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

输出格式

输出一个整数,表示第 nn 个合法正整数 xx。

数据范围

  • 1≤k≤181\le k\le 18;
  • 1≤n≤10181\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=1k=1 时,所有合法数从小到大依次以

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

开头。