折痕标签

难度：T2

【知识点：递归】【知识点：基本情况与返回顺序】

前置知识：函数、条件判断、整数拆位或按规则输出。

题目描述

你要按规则生成一排标签。每个标签只有两种：D 表示向下，U 表示向上。这里的“折痕”只是标签的名字，不需要真的折纸。

一排标签由两个参数确定：层数 $n$ 和正中央的标签 $c$。层数不是标签个数，$c$ 也不是整排所有标签的方向。

生成规则如下：

• $0$ 层没有任何标签，是空的一段。
• $1$ 层只有一个标签，就是给定的 $c$。
• 更高层由“左边一段、中央一个标签、右边一段”依次拼接而成：左段按相同规则生成，层数少 $1$，中央标签指定为 D；中间放本层的 $c$；右段也少 $1$ 层，但中央标签指定为 U。

注意：左右两段都要完整生成，不能各放一个字母就结束；每一段继续使用同样的规则。

看一个展开过程

例如最后一行，左段是已经生成好的 $2$ 层 D 标签串 DDU，右段是 $2$ 层 U 标签串 DUU。按顺序接在中央的 D 两侧，得到 DDUDDUU。

给定 $n$ 和 $c$，请输出这一排的完整标签串。

输入格式

一行一个整数 $n$ 和一个大写字符 $c$，用一个空格分隔。$c$ 只可能是 D 或 U。

输出格式

输出一行，只包含生成的 D、U 标签。标签之间不加空格，不输出表格中的分隔符。

样例输入

2 U

样例输出

DUU

样例说明

左右两段各为 $1$ 层，分别只有 D 和 U，中间放输入指定的 U，所以输出 DUU。

样例输入 2

3 D

样例输出 2

DDUDDUU

样例输入 3

1 U

样例输出 3

U

数据范围

$1\le n\le12$，$c$ 为 D 或 U。输入不会给出 $0$ 层；$0$ 层用于说明生成规则的终点。