九連環

題目敘述

姐姐最近給卦長玩九連環，卦長玩得很開心，很快就姐出來了。姐姐不開心，所以打算給卦長玩N連環，但是N連環卦長不會，所以想找你幫忙

九連環一開始的時候有9個環，全部按順序套在一個柄上每個環是互相牽制的，除了第１環，要取下或套上其他環是要在特定的狀態下才可以的，其規則有二：

• 規則一：第１環可以在任何時候套上或取下。
• 規則二：想套上或取下第N環 (N > 1)，就必須將第 N-1 環套在柄上，而第 1 到 N-2 環全部取下，如此才能套上或取下第 N 環。

輸入說明

輸入一個數字N,\(1 \leq\)N\(\leq 18\)，表示有N連環

輸出說明

按順序輸出N連環的解
Move ring n out，表示將第n個環取下
Move ring n in，表示將第n個環套上

詳請見範例輸入輸出

範例輸入 1

3

範例輸出 1

Move ring 1 out
Move ring 3 out
Move ring 1 in
Move ring 2 out
Move ring 1 out

範例輸入 2

5

範例輸出 2

Move ring 1 out
Move ring 3 out
Move ring 1 in
Move ring 2 out
Move ring 1 out
Move ring 5 out
Move ring 1 in
Move ring 2 in
Move ring 1 out
Move ring 3 in
Move ring 1 in
Move ring 2 out
Move ring 1 out
Move ring 4 out
Move ring 1 in
Move ring 2 in
Move ring 1 out
Move ring 3 out
Move ring 1 in
Move ring 2 out
Move ring 1 out

配分方法

• 20% 範例測資
• 20% N\(\leq 7\)
• 20% N\(\leq 12\)
• 40% 不限

Hints

備註

Judge Setting