Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if nn is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this until n is one. For example, the sequence for n=3n=3 is as follows:

3→10→5→16→8→4→2→13→10→5→16→8→4→2→1

Your task is to simulate the execution of the algorithm for a given value of n.

**Input**

The only input line contains an integer n.

**Output**

Print a line that contains all values of n during the algorithm.

**Constraints**

- 1≤n≤1061≤n≤106

**Example**

Input:`3`

Output:`3 10 5 16 8 4 2 1`

Code: Solution

//Weird Algorithm CSES solution codesagar.in import java.util.*; public class weirdAlgo { public static void main(String args[]) { // Weird Algorithm Scanner sc=new Scanner(System.in); long n=sc.nextLong(); while(n!=1){ if(n%2==0){ System.out.print(n+" "); n=n/2; } else{ System.out.print(n+" "); n=n*3+1; } } System.out.print(1+" "); } } //Weird Algorithm CSES solution codesagar.in