在五年级学生取得了最惊人的成功之后,小圆被信任负责教授六年级学生。
她的教室里有 $$$n$$$ 单人课桌。一开始小圆决定学生编号$$$b_i$$$ ($$$1 \le b_i \le n$$$) 坐在编号$$$i$$$ 的课桌上。还有无数编号为 $$$n + 1、n + 2、n + 3、\ldots$$$ 的学生在门口等候,希望能够向小圆本人学到一些东西。请注意,每个学生都有自己独特的编号。
每节课结束后,将按顺序发生以下情况。
1. 坐在课桌$$$i$$$ 的学生移动到课桌$$$p_i$$$。所有学生同时移动。
2. 如果一张桌子上有超过一名学生,则人数最少的学生保留该位置,其他学生将永远从班级中删除。
3. 对于所有空课桌,按升序排列,由外线编号最低的学生占用课桌。
请注意,最后每张桌子上又只有一名学生。保证 $$$p$$$ 的数字使得每节课后至少有一名学生被删除。查看第一个示例的解释以获得更好的理解。
几节课(可能是零节课)后,桌子 $$$i$$$ 被学生 $$$a_i$$$ 占据。给定值 $$$a_1、a_2、\ldots、a_n$$$ 和 $$$p_1、p_2、\ldots、p_n$$$,找到字典顺序最小的合适初始座位排列 $$$b_1、b_2、\ldots、b_n$$$。
排列是 $$$n$$$ 个不同整数的数组,从 $$$1$$$ 到 $$$n$$$,顺序任意。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是($$$2$$$ 出现两次)。 $$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
对于相同长度的两个不同排列 $$$a$$$ 和 $$$b$$$,如果在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,排列 $$$a$$$ 的元素比 $$$b$$$ 中的对应元素小,则 $$$a$$$ 按字典顺序小于 $$$b$$$。
输入
输入数据的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 教室中的课桌数量。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — 学生移动的课桌。保证 $$$p$$$ 至少有两个相等的元素。
第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 学生的最终座位。保证存在一个初始排列,从中可以获得座位$$$a$$$。
输出
在唯一的行中打印 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) - 按字典顺序描述六年级学生的初始座位的最小排列,可以导致最终座位 $$$a$$$。
示例
输入 #1
5 5 5 3 3 1 1 8 2 9 4
输出 #1
1 3 2 5 4
输入 #2
5 1 3 2 5 2 3 2 5 4 1
输出 #2
3 2 5 4 1
输入 #3
10 10 8 5 3 7 8 6 6 1 1 5 26 24 27 21 4 18 2 28 1
输出 #3
5 4 2 6 7 8 3 9 1 10
注意
第一个测试的描述如下:
第一张图显示了起始排列,这就是答案。然后坐在 $$$1, 2$$$ 课桌的学生被转移到 $$$5$$$ 课桌。此外,一名 $$$1$$$ 学生从 $$$5$$$ 课桌移动,而一名学生从 $$$4$$$ 磁盘转移到 $$$3$$$ 课桌。
因此,在所有这些传输之后,获得了第二幅图像中所示的排列。然后,在编号为$$$5$$$的课桌上,编号为$$$3$$$的学生被开除,在编号为$$$3$$$的课桌上,编号为$$$5$$$的学生被开除。 (因为他们的编号不是最小的)然后编号为 $$$6, 7$$$ 的新生坐在编号为 $$$2, 4$$$ 的课桌旁。第三张图片显示了这种排列(第一课结束后)。
$$$4$$$ 图片显示了第二节课之后所有多余座位被踢出之前的座位安排。第五张显示 $$$2$$$ 课后的最终座位。