给你一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p$$$$$^{\text{∗}}$$$。
对于长度为 $$$n$$$ 的任意排列 $$$q$$$,我们说索引 $$$j$$$ 占主导地位 索引 $$$i$$$ 当且仅当满足以下所有条件时:
- $$$j \gt i$$$,
- $$$p_j \gt p_i$$$,并且
- $$$q_j \gt q_i$$$。
还给您一个长度为 $$$n$$$ 的数组 $$$d$$$,其中 $$$d_i$$$ 表示主导索引 $$$i$$$ 的索引数量。
你的任务是构造一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$q$$$,这样对于每个索引 $$$i$$$ ($$$1 \le i \le n$$$),支配 $$$i$$$ 的索引 $$$j$$$ 的数量恰好是 $$$d_i$$$。
如果存在这样的$$$q$$$,则输出任何有效的。否则报告不存在。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$。保证 $$$p$$$ 形成从 $$$1$$$ 到 $$$n$$$ 的整数排列。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n$$$ ($$$0 \le d_i \le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例:
- 如果可以构造 $$$q$$$,则输出一行包含 $$$n$$$ 整数 $$$q_1, q_2, \ldots, q_n$$$ — 一个有效的排列。如果存在多个有效答案,您可以输出其中任何一个。
- 否则,输出$$$-1$$$。
示例
输入复制
732 3 11 0 043 4 1 22 1 1 052 3 1 4 52 2 1 1 011053 1 4 2 51 1 1 1 043 4 2 11 1 1 087 6 3 1 2 5 4 81 1 2 2 2 1 1 0
输出复制
1 2 3-12 1 4 3 512 4 1 3 5-11 2 4 6 5 3 7 8
注意
在第一个测试用例中,有效输出为 $$$q = [1, 2, 3]$$$:
- 对于 $$$i=1$$$,我们有 $$$p_1=2$$$ 和 $$$q_1=1$$$。索引 $$$j=2$$$ 支配 $$$i=1$$$,因为 $$$2 \gt 1$$$、$$$p_2=3 \gt p_1$$$ 和 $$$q_2=2 \gt q_1$$$。索引 $$$j=3$$$ 不支配 $$$i=1$$$,因为 $$$p_3=1 \lt p_1$$$。因此,恰好 $$$1$$$ 索引支配 $$$i=1$$$,它匹配 $$$d_1=1$$$。
- 对于 $$$i=2$$$,我们有 $$$p_2=3$$$ 和 $$$q_2=2$$$。唯一较大的索引是 $$$j=3$$$,但 $$$p_3=1 \lt p_2$$$,因此它不占主导地位。因此,$$$0$$$ 索引支配$$$i=2$$$,匹配$$$d_2=0$$$。
- 对于 $$$i=3$$$,没有更大的索引 $$$j \gt 3$$$,因此 $$$0$$$ 索引占主导地位,匹配 $$$d_3=0$$$。
在第二个测试用例中,$$$p = [3, 4, 1, 2]$$$ 和 $$$d = [2, 1, 1, 0]$$$。让我们看看$$$i=2$$$,其中$$$p_2=4$$$。由于不存在索引 $$$j \gt 2$$$ 和 $$$p_j \gt p_2$$$,因此没有索引可以支配 $$$i=2$$$。然而,数组 $$$d$$$ 需要 $$$d_2=1$$$,这使得无法构造有效的排列 $$$q$$$。因此,答案是 -1.