The jeweler has a balance with two cups, he can determine whether the masses of the weights lying on the two cups are equal, and if they are not equal – which cup has the lighter weight on it.
The mass of the piece of jewelry that the jeweler needs to determine is an integer from 1 to N. The jeweler must stock a set of weights (their masses must also be integers), with which the jeweler can determine any possible mass from 1 to N. To determine the mass, the jeweler can carry out any number of weighings, may use all the weights or only some of them, may place the weights on different scale pans.
Define a set of weights containing the minimum possible number of weights, using which you can determine any possible integer mass from 1 to N.
The program receives as input a natural number N (2 ≤ N ≤ 10
8) – the maximum allowable weight of a piece of jewelry.
The program should output several natural numbers not exceeding 10
9, – masses of weights in the minimum set required for solving the problem (it is allowed to use weights with a mass greater than N, if their mass does not exceed 10
9).
If the problem has multiple solutions, print any of them.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3 |
2 |
Let x – the product whose mass is to be determined. You need to put x on one scale, and on the other scale – a weight of 2. If x is lighter, then x = 1, if – x = 2, if x is heavier then x = 3. |
| 2 |
5 |
3 4 |
Let's show how to use the weights in 3 and 4 to determine all the masses from 1 to 5. The masses of 3 and 4 can be determined using the equalities x = 3 and x = 4. The mass of 1 can be determined using the equation x + 3 = 4 (a product and a weight of mass 3 are placed on one bowl, a weight of mass 4 is placed on the other bowl). The mass 2 can be determined, for example, by the condition x < 3 (a product is placed on one scale pan, and a weight of mass 3 is placed on the other) and also by checking using the previously described algorithm that x ≠ 1 . The mass 5 can be determined by weighing x > 4. |