思路

当 $n=1$ 时，输出 $1$ 即可。下面考虑 $n=2m+1\ge3$。

从 $13^2=169$、$14^2=196$、$31^2=961$ 出发，可以利用平方展开式在这些数字之间插入零，再在末尾补偶数个零。这样既能保留数字多重集，又能直接证明结果仍然是完全平方数。

做法

首先输出字符串 $196$，随后补 $n-3$ 个零。

然后枚举 $i=0,1,\ldots,m-1$，每次输出两个数：

• 按顺序拼接数字 $1$、$i$ 个零、数字 $6$、$i$ 个零、数字 $9$，最后补 $n-3-2i$ 个零。
• 按顺序拼接数字 $9$、$i$ 个零、数字 $6$、$i$ 个零、数字 $1$，最后补 $n-3-2i$ 个零。

所有零的数量均非负。总共输出 $1+2m=n$ 个数。直接使用字符串拼接即可，不能把最长 $99$ 位的数存入普通整数类型。

例如，$n=5$ 时，该方法可以输出 $19600,16900,96100,10609,90601$。这是一组与题面样例不同的合法答案。

正确性证明

首先证明平方性。第一项满足

$$196\cdot10^{n-3}=\left(14\cdot10^{m-1}\right)^2.$$

对于第 $i$ 次枚举，因为 $i+1\ge1$，以下展开式中各个非零十进制位互不重叠，不会产生进位：

$$\left(10^{i+1}+3\right)^2=10^{2i+2}+6\cdot10^{i+1}+9,$$$$\left(3\cdot10^{i+1}+1\right)^2=9\cdot10^{2i+2}+6\cdot10^{i+1}+1.$$

两式分别给出上述两种不含末尾补零的字符串。末尾补零的数量为 $n-3-2i=2(m-i-1)$，是非负偶数。因此，补零等价于将平方根再乘 $10^{m-i-1}$，结果仍然是完全平方数。

其次，每个构造出的数都恰有 $n$ 位，首位为 $1$ 或 $9$，没有前导零。所有数均含有一个 $1$、一个 $6$、一个 $9$ 和 $n-3$ 个零，数字多重集一致。

最后，同一类别中不同 $i$ 对应的三个非零数字位置不同；两种类别的首位不同。单独输出的 $196$ 后补零，与首位为 $1$ 的另一类在非零数字顺序上不同，也不可能与首位为 $9$ 的数相同。因此所有 $n$ 个数互不相同，满足题目全部要求。

部分分做法

子任务 1 可以从最小的 $n$ 位整数开始，依次枚举整数。维护下一个完全平方数及其平方根：当前枚举值等于它时，记录该平方数，再递增平方根并计算下一个平方数。按十个数字的出现次数分组，某组收集到 $n$ 个数时即可输出。即使采用递增维护，仍然需要经过大量非平方数。

子任务 2 可以直接枚举平方根，从 $10^{(n-1)/2}$ 开始递增，计算平方并按数字频次分组。这样跳过了所有非平方数，显著缩小搜索量。可以使用十进制大整数完成递增和平方运算，避免有限整数类型的溢出。

这两种搜索都会找到答案：上面的构造已经给出了处于 $n$ 位整数范围内的一组合法结果，因此完整枚举该范围的整数或平方根必然会遇到一组至少含 $n$ 个数的相同数字多重集。更大的数据需要使用直接构造消除搜索。

复杂度

直接构造的每个测试用例需要输出 $n$ 个 $n$ 位数，时间复杂度为 $O(n^2)$，与必要的输出长度同阶。本实现保存整组字符串，空间复杂度为 $O(n^2)$。一个输入文件的总输出数字数不超过 $100000$，时间复杂度为 $O(\sum n^2)$。

按十进制位计算大整数运算的成本，逐个整数枚举的时间上界为 $O(10^n n+10^{n/2}n^2)$；直接枚举平方根的时间上界为 $O(10^{n/2}n^2)$。两种搜索至多存储 $O(10^{n/2}n)$ 个十进制位，使用数字频次数组作为哈希分组键。