As a third-year student at Hogwarts School of Witchcraft and Wizardry, Harry has to study arithmetic (known as Arithmancy in the wizard world). Today’s Arithmancy lesson revolves around multiplication and division. Thus, for homework, Harry needs to write down $n$ integers $a_1, a_2, \ldots , a_ n$, according to the following rules:
$a_1 = 1$,
If $a_{i}$ is an odd integer, Harry has two choices: $a_{i+1} = 2 \cdot a_{i}$, or $a_{i+1} = 3 \cdot a_{i}$.
If $a_{i}$ is an even integer, Harry has three choices: $a_{i+1} = 2 \cdot a_{i}$, or $a_{i+1} = 3 \cdot a_{i}$, or $a_{i+1} = a_{i} / 2$.
Harry finished the homework by writing down $n$ integers in some arbitrary order. As Harry’s teacher, you want to check whether Harry did the homework correctly, i.e. whether it is possible to rearrange these $n$ integers, so that they satisfy the homework’s requirements.
The input contains multiple test cases, each test case is presented as below:
The first line contains an integer $n$ $(1 \le n \le 10^5)$.
The second line contains $n$ space-separated integers $x_1, x_2, \ldots , x_ n$ $(1 \le x_ i \le 10^{18})$.
The input ends with a line containing a single $0$, which is not a test case.
The sum of $n$ in all test cases does not exceed $10^6$.
For each test case, if it is not possible to rearrange the $n$ integers so that the homework’s requirements are satisfied, print ‘NO’ in a single line. Otherwise, print two lines:
The first line contains the string ‘YES’.
The second line contains $n$ space-separated integers $a_1, a_2, \ldots , a_ n$, satisfying the homework’s requirements. $a_1, a_2, \ldots , a_ n$ must be a permutation of $x_1, x_2, \ldots , x_ n$. If there are multiple solutions, you can output any of them.
Sample Input 1 | Sample Output 1 |
---|---|
5 1 2 4 4 8 5 1 2 4 8 8 0 |
YES 1 2 4 8 4 NO |