Chris will be getting braces very soon. He knows that he won't be able to eat candy after he gets his braces so he has decided to eat as much candy as possible each day prior to his dental appointment. Every day Chris goes to the candy store to buy some candy. Just so he can experience as many flavors as possible, Chris would put all the candy he bought that day at once in his mouth. On each consecutive day, Chris buys a completely different set of candy, not repeating any flavors that he had tasted the day before.

Chris wants to experience all possible combinations of candies in his mouth at the same time, therefore Chris will not buy the same set of candies from the candy store twice.

Steven, who works at the candy store, knows this. He knows that Chris will be happy if, by the time of his dental appointment in ~K~ days, he has experienced all combinations of candies available at the candy store exactly once. Can you help Steven come up with a set ~A~ of ~N~ candies to stock at the candy store each day that will make Chris happy?

Note that two sets of candies are considered equal if the number of candies of each type are all equal.

Constraints

~1 \le K \le 10^{12}~

~1 \le N \le 10^5~

~1 \le A_i \le 10^9~

Subtask 1 [5%]

~1 \le K \le 10^3~

Subtask 2 [65%]

~1 \le K \le 10^7~

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line of input contains an integer ~K~, the number of days before Chris has his dental appointment.

Output Specification

On the first line, you are to output one integer ~N~, the number of candies Steven should stock. Steven cannot stock more than ~10^5~ candies. ~N~ need not be minimal. If it is impossible for Steven to find at most ~10^5~ candies such that there are exactly ~K~ possible sets, simply output Sad Chris instead.

Otherwise, on the next line, you are to output ~N~ integers ~A_i~, the type of the ~i^{th}~ candy. All candies of the same type are identical.

If there are multiple correct answers, you may output any of them.

Sample Input

7

Sample Output

4
9 2 9 9

Explanation

Over his ~7~ days, Chris will eat the following combinations of candy:

$$\displaystyle (2)$$ $$\displaystyle (9)$$ $$\displaystyle (9, 2)$$ $$\displaystyle (9, 2, 9)$$ $$\displaystyle (9, 9, 9)$$ $$\displaystyle (9, 9, 9, 2)$$ $$\displaystyle (9, 9)$$