题目描述

作为学习动态规划的入门步骤，数字三角形问题极具代表性。下面我们将重新审视这个经典问题。

从下图三角形的底部任意位置出发，向上移动到上一行相邻的数字，从底部到顶部的最大总和为 $23$。

$$\begin{matrix} & & & 3 & & \\ & & 7 & & 4 & \\ & 2 & & 4 & & 6 \\ 8 & & 5 & & 9 & & 3 \end{matrix}$$

然而，作为整个问题的一个孤立答案，仅有最大总和是不够的。我们同样关心具体的路径轨迹。考虑下面的新三角形以及一个对应的字母三角形。从底部到顶部的最大总和为 $6$，经过两个 “$2$”。

$$\begin{matrix} & & & 2 & & \\ & & 1 & & 1 & \\ & 2 & & 1 & & 1 \\ 1 & & 1 & & 2 & & 1 \end{matrix}$$$$\begin{matrix} & & & a & & \\ & & a & & b & \\ & b & & a & & a \\ b & & a & & b & & a \end{matrix}$$

一条最佳轨迹可以通过将路径上所有对应字母按顺序连接成一个字符串来表示。

那么在上面的三角形中，从最后一行第一个位置出发的字典序最小的最佳轨迹是 “bbaa”。

从最后一行第二个位置出发的字典序最小的最佳轨迹是 “abaa”。

从最后一行第三个位置出发的字典序最小的最佳轨迹是 “baaa”。从最后一行第四个位置出发不存在任何最佳轨迹。

现在，需要编写一个程序来确定最后一行中至少能够引出一条最佳轨迹（从该位置出发的最佳轨迹）的所有位置。将这些可能的位置按照它们各自引出的字典序最小的最佳轨迹的字典序进行排序。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 4$)，表示有 $T$ 组测试数据。请注意，原题数据 $T=35$，洛谷数据中被分为 $11$ 个测试点。

对于每组测试数据，第一行包含一个整数 $N$ ($N \le 1500$)。接下来的 $N$ 行中，第 $i$ 行描述三角形的第 $i$ 行，包含 $n$ 对由一个正整数和一个小写字母组成的对。输入中的所有整数均为小于 $10$ 的正整数。

输出格式

对于每组查询，在一行中输出一串数字，表示按上述规则排序后的可能位置列表。如果两个位置对应的字典序最小的最佳轨迹相同，则优先输出索引较小的位置。

3
4
3 e
7 v 4 a
2 a 4 o 6 t
8 w 5 f 9 l 3 p
4
2 a
1 a 1 b
2 b 1 a 1 a
1 b 1 a 2 b 2 a
4
2 a
1 a 1 b  
2 b 1 a 1 a
1 b 1 a 2 b 1 a

3
4 2 3 1
2 3 1

提示

翻译由 DeepSeek V4 Pro 完成