CF1523C Compression and Expansion
题目描述
William 是一个非常喜欢提前规划的人。这就是为什么他每天早晨都会通过创建一个嵌套列表来安排即将要做的事情。
一个合法的嵌套列表，是指可以通过对只包含一个元素 $1$ 的列表进行若干次操作得到的列表。每次操作会在某个已有的条目 $a_1.a_2.a_3.\cdots.a_k$ 之后，在新的一行插入一个新条目，操作有两种类型：
1. 添加条目 $a_1.a_2.a_3.\cdots.a_k.1$（开始一个更深层级的列表），或者
2. 添加条目 $a_1.a_2.a_3.\cdots.(a_k+1)$（在当前层级继续添加）。
只有在操作后列表中没有出现两个完全相同的条目时，操作才允许进行。同时，如果我们将每个条目视为一个数字序列，那么所有条目的序列在字典序上必须始终保持递增。
在“备注”部分的图片中可以看到一些合法和不合法的列表示例。
当 William 想要将他的待办事项列表保存为 Word 文档时，他不小心按下了一个完全不同于他想要的“Ctrl-S”的快捷键。现在无法确定他到底按了什么快捷键，但触发后，列表中的所有条目都被替换成了一个数字：原本条目编号中的最后一个数字。
William 希望你帮他还原出一个符合要求的原始嵌套列表。
输入格式
每个测试用例包含多组数据。第一行包含一个整数 $t$（$1 \le t \le 10$），表示测试用例的组数。
每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^3$），表示列表的行数。
接下来的 $n$ 行，每行包含一个整数 $a_i$（$1 \le a_i \le n$），表示 William 的嵌套列表中每一行剩下的数字。
保证每组测试用例至少存在一种符合要求的原始列表。
保证所有测试用例中 $n$ 的总和不超过 $10^3$。
输出格式
对于每组测试用例，输出 $n$ 行，表示一个可能的合法嵌套列表，每行一个条目，能够还原为 William 给你的数据。
如果有多种答案，输出任意一种即可。
说明/提示
在第二个样例测试中，一个可能的合法列表如下：
1
1.1
1.1.1
1.1.2
1.2
1.2.1
2
2.1
2.2
这个列表可以通过如下操作序列得到：
1. 初始列表只有一个条目 $1$。
2. 通过第二种插入操作，在 $1$ 后插入 $2$。
3. 通过第一种插入操作，在 $1$ 后插入 $1.1$。
4. 通过第二种插入操作，在 $1.1$ 后插入 $1.2$。
5. 通过第一种插入操作，在 $1.1$ 后插入 $1.1.1$。
6. 通过第二种插入操作，在 $1.1.1$ 后插入 $1.1.2$。
7. 通过第一种插入操作，在 $1.2$ 后插入 $1.2.1$。
8. 通过第一种插入操作，在 $2$ 后插入 $2.1$。
9. 通过第二种插入操作，在 $2.1$ 后插入 $2.2$。
由 ChatGPT 4.1 翻译