题目描述

题目译自 Romanian Master of Informatics 2019 Day1 T1 「Devil's Share」

给你一个数字 $X$，魔鬼想要从中分得属于他的那份。他会拿走这个数字中长度为 $K$ 的最大子数字。你可以通过重新排列 $X$ 中的数字来尽量减少魔鬼的份额。

具体来说，你手上有 $S$ 个数字，这些数字的范围在 $1$ 到 $9$ 之间（包含 $1$ 和 $9$）。给定一个整数 $K$ $(1 \leq K \leq S)$，你需要用手上的所有数字组成一个数字 $X$，使得 $X$ 中长度为 $K$ 的最大子字符串尽可能小。

说明：$X$ 的长度为 $K$ 的子字符串是指由 $X$ 中连续的 $K$ 个数字按原有顺序组成的十进制整数。在数字 $X$ 中，这样的子字符串总共有 $S-K+1$ 个。

输入格式

输入包含多组数据。第一行包含一个整数 $T$ $(1 \leq T \leq 5\cdot 10^5)$，表示测试数据的组数。

每组输入数据包含两行，第一行包含一个整数 $K$，表示需要考虑的子字符串长度。第二行包含 $9$ 个以空格分隔的整数：$D_{1}, D_{2}, \ldots, D_{9}$ $(0 \leq D_{i}, D_{1}+D_{2}+\ldots+D_{9}=S, 1 \leq S \leq 10^5)$，其中 $D_{i}$ 表示你手上有多少个数字 $i$。

所有输入数据组的 $S$ 值之和不超过 $10^6$。

输出格式

对于每组测试数据，在单独的一行中输出你构造的数字 $X$。

如果存在多个 $X$ 都具有相同最小的长度为 $K$ 的最大子字符串，你可以输出其中任意一个。

3
2
1 1 2 0 0 0 0 0 0
7
2 4 2 0 0 6 2 2 2
7
3 3 3 0 0 6 2 2 2

2313
62616236261623778899
623616236162361778899

样例中包含三组测试数据。

在第一个样例中，$K=2$，你需要排列的数字是 1233。一个最优的 $X$ 是 2313，其长度为 $2$ 的子字符串分别是 23、31 和 13，最大的是 31。没有其他排列能使长度为 $2$ 的最大子字符串比 31 更小。另一个同样最优的 $X$ 是 3123，因为它长度为 2 的最大子字符串也是 31。

在第二个样例中，$K=7$，你需要排列的数字是 11222233666666778899。一个最优的 $X$ 是 62616236261623778899，其长度为 $7$ 的最大子字符串是 6261623。

在第三个样例中，$K=7$，你需要排列的数字是 111222333666666778899。一个最优的 $X$ 是 623616236162361778899，其长度为 $7$ 的最大子字符串是 6236177。

数据范围与提示

详细子任务附加限制及分值如下表所示。