C - Happy New Year! Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

10 進法で表記したときに 0,2 のみからなる正整数のうち、 K 番目に小さいものを求めてください。

制約

  • K1 以上 10^{18} 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

K

出力

答えを整数として出力せよ。
ただし、たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要がある。たとえば、 2.34e+22 のような指数表記や、 0523 のような先頭に不要な 0 を付けたような表記は許されない。


入力例 1

3

出力例 1

22

10 進法で表記した時に 0,2 のみからなる正整数を小さい方から並べると、 2,20,22,\dots となります。
このうち K=3 番目である 22 を出力してください。


入力例 2

11

出力例 2

2022

入力例 3

923423423420220108

出力例 3

220022020000202020002022022000002020002222002200002022002200

たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要があることに注意してください。

Score : 300 points

Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

  • K is an integer between 1 and 10^{18} (inclusive).

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer as an integer.
Here, the exact value must be printed as an integer, even if it is big. Exponential notations such as 2.34e+22, for example, or unnecessary leading zeros such as 0523 are not allowed.


Sample Input 1

3

Sample Output 1

22

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.


Sample Input 2

11

Sample Output 2

2022

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.