题目描述

九连环游戏的历史非常悠久，据说起源于战国时期。九连环由九个相互连接的环组成，这九个环套在一个中空的长形柄中。九连环的玩法是要将这九个环从柄上解下来。解下所有九个环需要解341步，因此人们需要有耐心。 九连环的游戏规则如下：

1. 第1环可以自由上下；
2. 而上/下第 n 环时（n>1），则必须满足以下两个条件：

• 前n-1个环在架上；
• 前n-2个环全部在架下。

给定环的个数N，输出将N个环解下需要的步骤。

输入格式

一个正整数n(n ≤ 20)，代表环的个数。

输出格式

若解下N环的最优解法由k步构成，则： 前k行输出操作步骤。若当前放上第t个环，则输出up t；若当前取下第t个环输出down t。第k+1行，输出k。

3

down 1
down 3
up 1
down 2
down 1
5

数据范围与提示

n ≤ 20