Polycarp likes to play with numbers. He takes some integer number xx, writes it down on the board, and then performs with it n?1n?1 operations of the two kinds:

divide the number xx by 33 (xx must be divisible by 33);
multiply the number xx by 22.
After each operation, Polycarp writes down the result on the board and replaces xx by the result. So there will be nn numbers on the board after all.

You are given a sequence of length nn — the numbers that Polycarp wrote down. This sequence is given in arbitrary order, i.e. the order of the sequence can mismatch the order of the numbers written on the board.

Your problem is to rearrange (reorder) elements of this sequence in such a way that it can match possible Polycarp’s game in the order of the numbers written on the board. I.e. each next number will be exactly two times of the previous number or exactly one third of previous number.

It is guaranteed that the answer exists.

Input
The first line of the input contatins an integer number nn (2≤n≤1002≤n≤100) — the number of the elements in the sequence. The second line of the input contains nn integer numbers a1,a2,…,ana1,a2,…,an (1≤ai≤3?10181≤ai≤3?1018) — rearranged (reordered) sequence that Polycarp can wrote down on the board.

Output
Print nn integer numbers — rearranged (reordered) input sequence that can be the sequence that Polycarp could write down on the board.

It is guaranteed that the answer exists.

Examples
Input
6
4 8 6 3 12 9
Output
9 3 6 12 4 8
Input
4
42 28 84 126
Output
126 42 84 28
Input
2
1000000000000000000 3000000000000000000
Output
3000000000000000000 1000000000000000000
Note
In the first example the given sequence can be rearranged in the following way: [9,3,6,12,4,8][9,3,6,12,4,8]. It can match possible Polycarp’s game which started with x=9x=9.
題意：給你一組序列，要你重新排列這一組序列，使得第i位的元素，要么是i+1位置元素的三倍，要么是i+1元素的二分之一。
一開始想簡單了，就一直wa在了第四個樣例。。
如果某個元素和當前元素有題意所給的關系，那么我們就給這兩個元素下標連一條邊。這樣下來就建成了一個圖。找到入度為0的位置dfs，類似于拓撲排序。這樣就可以構造出那樣的一組序列了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e2+101; ll a[maxx]; int b[maxx]; int in[maxx]; int vis[maxx]; vector<int> p[maxx]; int n;inline void dfs(int x,int &cnt) {for(int i=0;i<p[x].size();i++){int to=p[x][i];if(!vis[to]){b[++cnt]=to;dfs(to,cnt);}} } int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[j]*3ll==a[i]) p[i].push_back(j),in[j]++;if(a[j]*2ll==a[i]) p[j].push_back(i),in[i]++;}}int pos;for(int i=1;i<=n;i++){if(!in[i]){pos=i;break;}}int cnt=0;b[++cnt]=pos;vis[pos]=1;dfs(pos,cnt);for(int i=1;i<=n;i++) printf("%I64d%c",a[b[i]],i==n?'\n':' '); }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Divide by three, multiply by two（dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。