单点时限: 2.0 sec
内存限制: 256 MB
给定长度为 N 的字符串 S,要构造一个长度为 N 的字符串 T。起初,T 是一个空串,随后反复执行下列两个操作中的任意一个,最终 目标是构造字典序尽可能小的字符串 T。
操作一:从 $S$ 的头部取一个字符,加到 $T$ 的尾部。
操作二:从 $S$ 的尾部取一个字符,加到 $T$ 的尾部。
例如:输入 $N=6$,S=ACDBCB
;构造的 T=ABCBCD
具体按下图进行操作。
第 1 行:整数 $T(1≤T≤10)$ 为问题数。
第 2 行:第一个 问题中的 $N(1≤N≤500)$,表示字符串 $S$ 的长度。
第 3 行:输入一个字符串 $S$,只包含大小写英文字母。
第 4 ~ 2*T+1 行:后面问题的数据 ,格式与第 1 个问题相同。
对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0:
等),然后 输出由 S 字符串构造出来的 字典序尽可能小的字符串 T。
3 2 ba 5 SORTS 10 Sarumanarm
case #0: ab case #1: SORST case #2: Samranamru