九连环

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

不知道大家有没有玩过一个叫做 九连环 的玩具,如下图所示。

如果你不了解九连环,那玄黄就带你领略九连环的奥妙: 
九连环是我国传统的民间智力玩具,玩具上面有九个连环套在杆上,目标就是通过一定的方式将九个连环从杆上全部取下来。 
玩法是这样的: 
1、对每个环,有2种操作:把这个环放到杆上或把这个环从杆上取下 
2、你可以随意的对第1个环进行操作 
3、如果你想对第i个环(i>1)进行操作,你必须将第i-1个环放在杆上,且必须把前i-2个环从杆上取下

 

Input

输入一个整数n ( 0

Output

输出把所有连环取下来的最少操作步骤,每一步占一行,输出一个整数i和操作”UP”或者”DOWN”,代表将第i个环放到杆上或从杆上取下来,整数和操作用空格分开。详情见示例输出。

Sample Input

4

Sample Output

2 DOWN
1 DOWN
4 DOWN
1 UP
2 UP
1 DOWN
3 DOWN
1 UP
2 DOWN
1 DOWN

Hint

Source

玄黄