给定一棵有 $n$ 个节点的树，根节点为 $1$，每个节点 $i$ 都有一个给定的权值 $a_i$（$i = 1, 2, \dots, n$）。

我们定义 $d(x, y)$ 为节点 $x$ 到节点 $y$ 的最短路径上的边数，并定义多重集 $p(x, k) = \{a_y \mid y \text{ 在 } x \text{ 的子树中且 } d(x, y) \le k\}$。注意这里 $a_x \in p(x, k)$。

我们定义任意集合的得分为该集合中任意两个数异或值的平方和。例如，集合 $\{1, 1, 2, 3\}$ 的得分为： $$(1 \oplus 1)^2 + (1 \oplus 2)^2 + (1 \oplus 3)^2 + (1 \oplus 2)^2 + (1 \oplus 3)^2 + (2 \oplus 3)^2 = 27$$ 其中 $\oplus$ 表示按位异或运算。

现在给定参数 $k$，你需要计算每个节点 $x$ 对应的 $p(x, k)$ 的得分。

输入格式

第一行包含两个整数 $n, k$ ($1 \le k \le n \le 100000$)，分别表示树的节点数和题目描述中的参数。

第二行包含 $n$ 个整数，第 $i$ 个数 $a_i$ ($1 \le a_i \le 10^9$) 表示第 $i$ 个节点的权值。

第三行包含 $n - 1$ 个整数，第 $i$ 个数 $f_{i+1}$ ($1 \le f_{i+1} \le i$) 表示第 $(i+1)$ 个节点的父节点。

输出格式

输出 $n$ 行，第 $i$ 行包含一个整数，表示 $p(i, k)$ 的得分。注意答案可能非常大，请输出其对 $2^{64}$ 取模的结果。

样例

样例输入 1

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

样例输出 1

86
98
0
0
4
0