Migrated from Lutece 3112 Mon panache!Ⅱ

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：启发式分裂、可持久化线段树、树状数组、STL

法国国王亨利四世经常在战斗中喊：“跟随我的白色羽毛！”（法语：“Ralliez-vous à mon panache blanc!”）

鱼鹰（鹗）凭借自己的翅膀飞翔，能从遥远的空中观察海面，还能观察海底。

黑鸢总是乘着上升气流，捕捉海边的螃蟹等生物。

所谓panache，就是心意気（勇气，气势）。

是健一郎教给圭的panache，也是圭教给心铃的panache。

是生活的心意気，也是艺术的心意気。

夏目圭正在准备“新·摩尔展”的展出作品，但这一次的作品形式十分新颖。

在他的画布上画着长为 $n$ 的数组 $\{a_n\}$ ，他将按照顺序在上面涂上颜料，初始时数组中的每个元素都没有被颜料覆盖。

他总共会进行 $n$ 次操作，在第 $i$ 次操作中，他将选择一个还未被颜料覆盖的下标 $p_i$ ，然后用颜料将这个位置上的数覆盖。

定义一个子数组的美丽度为它的逆序对数量，圭想要知道在他的每一次操作之前，所有不包含被颜料覆盖的位置的子数组的美丽度的最大值。

你可能会对圭提到的一些“新·艺术”名词有所疑惑，下面是对它们的解释：

• 子数组：在原数组的头部和尾部各删去若干元素（可能为 $0$ 个）后剩下的部分称为原数组的子数组。
• 逆序对：对于子数组 $a_l,a_{l+1},\cdots,a_{r-1},a_r$ ，它的逆序对数量等于符合以下条件的二元组 $(i,j)$ 的数量：
  • $l\le i<j\le r$
  • $a_i>a_j$

Input

输入的第一行包括一个正整数 $n$ ，表示初始时画布上数组的长度。

第二行包括一个长为 $n$ 的序列 $\{a_n\}$ ，表示数组中每个元素的值。

第三行包括一个长为 $n$ 的序列 $\{p_n\}$ ，表示圭在画布上涂上颜料的顺序， $p_1$ 表示他第一次操作会给第 $p_1$ 个元素涂上颜料，依此类推。

注意，由于艺术家的奇怪癖好，圭给出的序列经过加密，但是他好心地告诉了你解密的方式：

• 设 $ans_i$ 为进行第 $i$ 次操作之前，所有不包含被颜料覆盖的位置的子数组的美丽度的最大值。
• 令 $p'_i=p_i\oplus ans_i$ ，即可得到第 $i$ 次操作真实的下标 $p'_i$ ，其中 $\oplus$ 是按位异或运算符。

数据保证正确解密后得到的序列 $\{p'_n\}$ 为 $1\sim n$ 的排列。

Output

输出一行共 $n$ 个数，包括 $ans_1,ans_2,\cdots,ans_n$ ，其含义如上所述。

Samples

5
4 3 1 1 1
5 4 5 3 1

7 0 0 0 0

10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6

20 11 7 2 0 0 0 0 0 0

Constraints

$1\le n\le 1\times 10^5,1\le a_i\le n$ ，保证正确解密后得到的序列 $\{p'_n\}$ 为 $1\sim n$ 的排列。

Note

样例1解释：解密后的 $\{p'_n\}$ 排列为 $\{2,4,5,3,1\}$ 。

样例2解释：解密后的 $\{p'_n\}$ 排列为 $\{1,3,8,7,9,2,4,5,10,6\}$ 。

Resources

2024 UESTC ICPC Training for Data Structures