Description

在 LBA 的璀璨星空中，可比豆是最耀眼的那颗星。无数小迷妹为他痴狂，有 $k$ 个小迷妹自发组成了 $n$ 个应援团体。

这些小团体宛如一棵参天大树：每个小迷妹是一片独立的叶子，而她们又聚合成更大的枝干，最终汇聚成那最粗壮的树干——可比豆全球后援会。

这棵由小迷妹们组成的树有 $n$ 个节点，根节点是"可比豆全球后援会"（编号为 $1$）。每个叶子节点代表一个小迷妹，她有一个初始的号召力值 $w_i \in [1, n]$。

非叶子节点的号召力则由其直接子节点的号召力决定——取它们的中位数。具体来说，如果一个节点有 $s$ 个子节点，将它们的号召力从小到大排序后，取第 $\lceil \frac{s}{2} \rceil$ 个值作为该节点的号召力。

现在，小迷妹们迎来了千载难逢的机会：她们有 $m$ 次与可比豆见面的机会！每次见面可以让任意一个小迷妹（即任意一个叶子节点，允许重复选择）的号召力变为 $[1, n]$ 中的任意整数。

作为小迷妹中最聪明的你，需要制定最优的见面安排方案，让"可比豆全球后援会"（根节点）的号召力达到最大，以备不时之需，你需要对 $m\in[0,k]$ 求出答案。

形式化题意

给定一棵 $n$ 个点，$k$ 个叶子的根为 $1$ 的树，给定叶子结点的权值，值域为 $[1,n]$，非叶子结点的权值为其子节点的权值的中位数。

现在可以进行 $m$ 次操作，每次操作选择一个叶子节点（允许重复选同一个叶子），将其权值改为 $[1,n]$ 中的任意整数。

求最大化根节点权值，你需要对 $m\in [0,k]$ 求出答案。

长度为 $n$ 的序列的中位数定义为将序列从小到大排序后第 $\lceil \frac{n}{2}\rceil$ 的数。

Input Format

第一行两个整数 $n,k$，含义如题所述。

第二行 $n$ 个整数，对于第 $i$ 个数 $w_i$，

• 若 $w_i=0$，表示编号为 $i$ 的节点是非叶子节点。
• 若 $w_i\ne 0$，表示编号为 $i$ 的点是叶子结点，其权值为 $w_i$。

第三行 $n-1$ 个整数，第 $i$ 个整数 $fa_{i+1}$ 表示 $i+1$ 的父亲。

特别地，根节点不是叶子节点，保证 $w_1=0$。

Output Format

记 $ans_i$ 为 $m=i$ 时的答案，你需要输出一行，一个整数，表示 $\bigoplus\limits_{i=0}^k(i\times ans_i)$ 的结果，其中 $\oplus$ 表示按位异或。

5 4
0 1 2 3 4
1 1 1 1

16

10 6
0 0 1 0 0 3 3 4 5 5
1 1 2 2 1 1 5 4 4

51

Hint

样例解释 1

• 对于 $m=0$，此时 $1$ 号点的权值为序列 $\{1,2,3,4\}$ 的中位数为 $2$。
• 对于 $m=1$，一种最优策略是将 $2$ 号点的权值改为 $3$，此时 $1$ 号点的权值为序列 $\{2,3,3,4\}$ 的中位数为 $3$。
• 对于 $m=2$，一种最优策略是将 $2,3$ 号点的权值改为 $4$，此时 $1$ 号点的权值为序列 $\{3,4,4,4\}$ 的中位数为 $4$。
• 对于 $m=3,4$，$1$ 号点的权值为 $5$。

因此答案为 $0\times 2 \oplus 1\times 3\oplus 2\times 4 \oplus 3\times5 \oplus 4\times5=16$。

样例解释 2

对于 $m\in[0,6]$，答案分别为 $3,3,4,10,10,10,10$。

数据范围

对于 $100\%$ 的数据：$1\le k<n\le 2\times 10^6,\forall i\in[2,n],\; fa_i<i,w_i\in[0,n]$。