Calculating Collatz Cousins Define the function f(n) for a positive integer n as follows:


n / 2, if n is even
3 * n + 1, if n is odd


If you repeatedly apply this function to any n greater than 0, the result always seems to converge to 1 (though nobody's been able to prove that yet). This property is known as the Collatz Conjecture.

Define an integer's stopping time as the number of times you have to pass it through the Collatz function f before it reaches 1. Here are the stopping times of the first 15 integers:

1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17


Let's call any set of numbers with the same stopping time Collatz cousins. For example, 5 and 32 are Collatz cousins, with a stopping time of 5.

Your task: write a program or function that takes a nonnegative integer and generates the set of Collatz cousins whose stopping time is equal to that integer.

Input

A nonnegative integer S, given via STDIN, ARGV, or function argument.

Output

A list of all numbers whose stopping time is S, sorted in ascending order. The list may be output by your program, or returned or output by your function. Output format is flexible: space-separated, newline-separated, or any standard list format of your language is fine, as long as the numbers are easily distinguishable from one another.

Requirements

Your submission must give correct results for any S ≤ 30. It should finish in seconds or minutes, not hours or days.

Examples

0  -&gt; 1
1  -&gt; 2
5  -&gt; 5, 32
9  -&gt; 12, 13, 80, 84, 85, 512
15 -&gt; 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768


Here is a Gist of the output for S = 30.

This is code-golf: shortest program in bytes wins. Good luck!
Mathematica, 98 92 89 bytes

This solution solves S = 30 immediately:

(p={0};l={1};Do[l=Complement[##&amp;@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&amp;/@l,p=p⋃l],{#}];l)&amp;


This is an unnamed function taking S as its only parameter and returning a list of the Collatz cousins.

The algorithm is a simple breadth-first search. The Collatz cousins for a given S are all the integers that can be reached from the Collatz cousins for S-1 via 2*n or odd numbers that can be reached via (n-1)/3. We also need to ensure that we only produce those integers which were reached for the first time after S steps, so we keep track of all previous cousins in p and remove those from the result. Since we're doing that anyway, we can save a few bytes by computing the steps from all previous cousins (not just those from S-1) to save a few bytes (that makes it slightly slower, but not noticeably for the required S).

Here is a slightly more readable version:

(
  p = {0};
  l = {1};
  Do[
    l = Complement[
      ## &amp; @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} &amp; /@ l,
      p = p ⋃ l
    ]~Cases~_Integer,
    {#}
  ];
  l
) &amp;