UOJ Logo Universal Online Judge

UOJ

#639. 【美团杯2021】C. 查查查乐乐II

附件下载 统计

前情提要:“查查查乐乐”是一段古老神秘的咒语,只有被选中的魔法师才有资格使用这一段咒语并享用它所带来的力量;而如果这段咒语出现在了不具资格的魔法师的口中,这个魔法师将会遭到咒语的反噬并付出可怕的代价。

蒜斜是北京魔法大学(PKMU)的一名博士研究生,他的研究方向就是”查查查乐乐“的危害:虽然单独念出”查查查乐乐“的风险早已被探明,但是关于那些包含”查查查乐乐“的咒语是否存在同样的风险,目前魔法学界还没有一个统一的定论。

蒜斜现在的研究是关于 $k$-复合”查查查乐乐”咒语的:一个只包含”查“和”乐“的咒语是 $k$-复合“查查查乐乐”的当且仅当”查查查乐乐“在这个咒语中以子序列的形式出现了恰好 $k$ 次。举例来说,咒语“查查查乐乐乐”就是 $3$-复合“查查查乐乐”的,而咒语 ”查查查乐查乐乐“ 是 $6$-复合的。

在研究的过程,蒜斜需要经常咏唱 $k$-复合”查查查乐乐“ 咒语。为了节约研究时间,蒜斜希望对每一个 $k \in [1, n]$ 都找到最短的那个 $k$-复合”查查查乐乐“咒语。

输入格式

输入一行包含一个整数 $n$,表示蒜斜关心的 $k$ 的取值范围。

输出格式

输出 $n$ 行每行包含一个字符串,其中第 $i$ 行表示的是长度最短的 $i$-复合”查查查乐乐“咒语。在输出的时候,你需要用 x 来代替”查“,用 l 来代替”乐“。

特别地,如果长度最短的 $i$-复合”查查查乐乐“咒语有很多,你需要输出字典序最小的那一个;如果不存在 $i$-复合”查查查乐乐“咒语,你需要输出 -1

样例一

注意,该样例不会被包含在正式的测试数据里。

input

10

output

xxxll
-1
xxxlll
xxxxll
-1
xxxllll
-1
-1
xxxllxll
xxxxxll

限制与约定

Small Task: $n = 100$

Large Task: $n = 10^5$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$