Towers of Hanoi (ハノイの塔)

3本の棒（左が1番、中央が2番、右が3番）が与えられ、最初の棒には大きさが異なる円盤が n 枚積まれています。円盤は上から下に向かって大きくなるように並べられています。できる操作は、ある棒の一番上の円盤を別の棒に移し、その棒にあるより大きな円盤の上に置くことのみです。つまり、小さな円盤の上に大きな円盤を置くことはできません。

目標は、はじめの棒にある円盤をすべて3本目の棒へ移すのに必要な操作をすべて出力することです。その際、移動回数は最小でなければなりません。

Input

入力として、最初の棒にある円盤の枚数を表す整数 n (1 ≤ n ≤ 16) が1つ与えられます。

Output

最初の棒から3本目の棒へ円盤を移動するために必要な一連の操作をすべて出力してください。各棒上の円盤は、必ずすべて下に行くほど大きい円盤になるように維持する必要があります。出力される操作の総数は、 回を超えないようにしてください。

Examples