乗算と除算

ゲームを考えてみましょう。初期値として整数 x が与えられ、実行できる操作は次の2つだけです:

• (ただし x が 3 で割り切れる場合のみ可能)

この初期整数 x に対して、これらの操作をランダムに適用して得られた n 個の値が与えられます。課題は、実際に行われた操作の順序を元に戻し、そのときに得られた値を正しい手順で並べ替えて出力することです。

入力

最初の行には整数 n (1 ≤ n ≤ 60) が1つ与えられます。

次の行には、ランダムに得られた n 個の整数がスペース区切りで入力されます。これらの整数の絶対値は を超えません。

出力

操作の正しい順序に従って、n 個の整数をスペース区切りで出力してください。

例

解説