题目描述

A positive integer $X$ is said to be a lunlun number if and only if the following condition is satisfied:

• In the base ten representation of $X$ (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most $1$.

For example, $1234$, $1$, and $334$ are lunlun numbers, while none of $31415$, $119$, or $13579$ is.

You are given a positive integer $K$. Find the $K$-th smallest lunlun number.

当且仅当满足以下条件时，正整数 $X$ 才被称为伦伦数：

• 在 $X$ 的十进制表示中（不含前导零(不含前导零）中，每一对相邻的两位数，其绝对差最多为 $1$ 。

例如， $1234$ 、 $1$ 和 $334$ 都是伦数，而 $31415$ 、 $119$ 和 $13579$ 都不是。

给你一个正整数 $K$ 。求最小的 $K$ 个伦数。

输入格式

输入内容按以下格式标准输入：

$K$

输出格式

打印答案。

样例 #1

样例输入 #1

15

样例输出 #1

23

样例 #2

样例输入 #2

1

样例输出 #2

1

样例 #3

样例输入 #3

13

样例输出 #3

21

样例 #4

样例输入 #4

100000

样例输出 #4

3234566667

说明

数据规模与约定

• $1 \leq K \leq 10^5$
• 所有输入值均为整数。

样例 $1$ 解释

我们将按升序列出 $15$ 最小的伦琴数：
$1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ , $9$ , $10$ , $11$ , $12$ , $21$ , $22$ , $23$ .
因此，答案为 $23$ 。

样例 $4$ 解释

注意，答案可能不适合 $32$ /位有符号整数类型。