题目描述

一个正整数 $x$ 被称为美丽整数，当且仅当 $x$ 是一个 $9$ 位的整数，并且其十进制表示 $S_1\ldots S_9$（$S_i$ 表示 $x$ 的十进制表示的第 $i$ 位数字）满足以下所有条件：

• $S_1$ 不是 0。
• $S_1 = S_2$。
• $S_5 = S_6$。
• $S_7 = S_9$。

例如，$998244353$ 和 $333333333$ 都是美丽整数。$111112222$ 不是美丽整数，因为 $S_5 \neq S_6$。

给定一个正整数 $N$，请输出按从小到大顺序排列的第 $N$ 个美丽整数。

输入格式

输入为一行，包含一个正整数 $N$。

输出格式

输出按从小到大顺序排列的第 $N$ 个美丽整数。

样例 1

输入

3

输出

110000020

样例 2

输入

882436

输出

998244353

样例 3

输入

2023

输出

110200222

说明/提示

约束

• $N$ 是正整数。
• 美丽整数的个数不少于 $N$。

样例解释 1

将美丽整数按从小到大排列，依次为 $110000000,\ 110000010,\ 110000020,\ \ldots$。

由 ChatGPT 4.1 翻译