题目描述

33DAI 在给一道题造测试数据。他打算摆放一列数字，其中数字 $1$ 到 $n$ 的出现次数分别是 $c_1, c_2, \dots, c_n$（可能出现次数为 $0$），设总长度为 $m = \sum_{i=1}^{n} c_i$。

他还有一个额外的要求：相邻两个数字不能相同。

请你帮他给出一种满足要求的摆放方案；如果不存在这样的方案，输出 -1。

本题的答案不唯一，只要给出任意一种满足要求的方案都算正确。

输入格式

输入的第一行是一个整数 $t$，表示测试用例组数。

接下来依次给出 $t$ 组测试用例，每组测试用例的格式为：

• 第一行一个整数 $n$；
• 第二行 $n$ 个整数 $c_1, c_2, \dots, c_n$。

输出格式

对每组测试用例：

• 若存在满足要求的方案，输出一行 $m$ 个整数，相邻两个整数之间用一个空格隔开，表示你摆放的这一列数字；
• 若不存在，输出一行 -1。

3
3
1 2 1
4
1 2 3 1
2
2 1

2 1 2 3
3 2 3 1 3 4 2
1 2 1

样例 1 解释

第 1 组：$n = 3$，$c = (1, 2, 1)$，所以 $m = 1 + 2 + 1 = 4$，数字 $1, 2, 3$ 分别要出现 $1, 2, 1$ 次。样例输出 2 1 2 3：数字 $1$ 出现 $1$ 次、数字 $2$ 出现 $2$ 次、数字 $3$ 出现 $1$ 次，并且相邻两项都不同，满足要求。

第 2 组：$n = 4$，$c = (1, 2, 3, 1)$，所以 $m = 7$。样例输出 3 2 3 1 3 4 2：数字 $1, 2, 3, 4$ 分别出现 $1, 2, 3, 1$ 次，并且相邻两项都不同，满足要求。

第 3 组：$n = 2$，$c = (2, 1)$，所以 $m = 3$。样例输出 1 2 1：数字 $1$ 出现 $2$ 次、数字 $2$ 出现 $1$ 次，并且相邻两项都不同，满足要求。

样例 2

见 gap2.in 与 gap2.ans。

样例 3

见 gap3.in 与 gap3.ans。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 100$；
• $1 \le n \le 10^5$；
• $0 \le c_i \le 10^5$；
• 每组测试用例的 $\sum_{i=1}^{n} c_i$ 不超过 $10^5$，所有测试用例的 $\sum_{i=1}^{n} c_i$ 之和也不超过 $10^5$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。