Background

又是一年圣诞节，温水佳树在家中准备为温水和彦开生日宴。

『兄长大人，又到圣诞节了呢。』

『兄长大人，今年有人给你送友情巧克力吗？』

『生日快乐，兄长大人。』

Description

温水佳树想要装饰一棵圣诞树，但是她身高不济，够不到较高的位置，所以她叫来了温水和彦搬来梯子。

温水家的圣诞树可以视作一棵由 $n$ 个节点构成的树，其中节点 $1$ 是根。方便起见，输入将以父亲表示法的形式给出，$f_i(2\leq i \leq n)$ 表示节点 $i$ 的父亲。每个节点有一个彩灯，安装顺序由排列 $p$ 决定：第 $i$ 次操作将彩灯安在节点 $p_i$ 上。

每当安装第 $i$ 个彩灯前（$i \geq 2$），温水和彦会将梯子顶调整到 $p_i$ 与已安装的某个彩灯节点（即 $p_1, p_2, \dots, p_{i-1}$）的最近公共祖先（LCA）处，且该 LCA 的深度必须尽可能大。你需要输出所有 $i=2,3,\dots,n$ 时梯子顶节点编号的异或和。

Constraints and Subtasks

对于所有测试数据，满足：

• $1 \leq n \leq 10^7$
• $1 \leq f_i < i$
• $p$ 是 $1$ 到 $n$ 的排列。
• 所有的输入均为整数。

另外，还有一些测试点满足特殊要求。

Input

输入格式如下：

$ \boxed{ \begin{aligned} & n \\ & f_2 \quad f_3 \quad \dots \quad f_n \\ & p_1 \quad p_2 \quad \dots \quad p_n \\ \end{aligned} } $

Output

输出一行一个整数，表示 $i=2$ 到 $n$ 时每个步骤答案的异或和。

Sample

6
1 1 2 2 5
3 5 1 4 6 2

5