配点 : 800 点
只在玩游戏中大受欢迎。总共有4 匹参与游戏。
問題文
1 每个输入文件 T 个测试用例被提供。在每个测试用例中,有正整数 M, N 和整数 可以获得第 A_1, A_2, \ldots, A_M ,回答以下问题。
M 只兔子和 N 只猫。兔子有 1, 2, \ldots, M ,猫有 1, 2, \ldots, N 。
2 只兔子和 2 选择几只猫的方法 \binom{M}{2} \binom{N}{2} 对于每条街道,被选中的 4 只正好 1 次进行游戏,每次游戏中 4 从___匹中决出获胜者 1 决定了___匹。然后,
- 兔子 i (1 \le i \le M获胜的次数 a_i
- 猫 j (1 \le j \le N获胜的次数 b_j
被记录了。
根据游戏结果 (a_1, a_2, \ldots, a_M) = (A_1, A_2, \ldots, A_M) 判断是否可能成为___,如果可能,则在该条件下,作为数列 (b_1, b_2, \ldots, b_N) 的可能序列中求字典序最小的。
制約
- 1 \le T \le 10^5.
- 2 \le M \le 10^6.
- 2 \le N \le 10^6.
- 0 \le A_i \le (M-1) \binom{N}{2} (1 \le i \le M).
- 1 个输入文件中的 M 的总和是 10^6 以下.
- 1 个输入文件中的 N 的总和是 10^6 以下.
入力
标准输入 1 排队测试用例数 给出了 T 。之后,T 测试用例均按以下格式给出。
M N A_1 A_2 \cdots A_M
出力
对于每个测试用例依次输出 1 行,如下所示。
(a_1, a_2, \ldots, a_M) = (A_1, A_2, \ldots, A_M) 如果可能成为___, 在该条件下,作为数列 (b_1, b_2, \ldots, b_N) 的可能序列中字典序最小的,以以下格式输出。
b_1 b_2 \cdots b_N
(a_1, a_2, \ldots, a_M) = (A_1, A_2, \ldots, A_M) 如果不可能成为___,
-1
。
入力例 1
3 2 3 0 1 4 3 2 1 1 0 4 5 30 30 30 30
出力例 1
0 0 2 0 2 12 -1
1 假设第___个测试用例的游戏结果如下:
- “兔子” 1,兔子 2,猫 1,猫 2”被选中的游戏中,兔子 2 为胜者
- “兔子” 1,兔子 2,猫 1,猫 3”被选中的游戏中,猫 3 为胜者
- “兔子” 1,兔子 2,猫 2,猫 3”被选中的游戏中,猫 3 为胜者
此时,(a_1, a_2) = (0, 1) = (A_1, A_2) 变为(b_1, b_2, b_3) = (0, 0, 2) 变为。
一方 (b_1, b_2, b_3) 是 在 (0, 0, 2) 不会比猫的字典序小,(0, 0, 2) 成为答案。