给定一棵包含 $N$ 个顶点的有根树，以及整数 $R$ 和 $M$。顶点编号为 $1$ 到 $N$，其中顶点 $1$ 为根。树中其余每个顶点都有唯一的父节点。

如果选择一个顶点 $s$，它及其所有距离为 $R$ 或更小的后代（即可以通过从 $s$ 向下沿边到达的顶点）都会被感染，其中距离定义为顶点间的边数。当且仅当顶点 $u$ 和 $v$ 均未被感染，且它们之间路径上的感染顶点数量不超过 $M$ 时，称顶点 $u$ 可从顶点 $v$ 到达（反之亦然）。

对于每个可能选择的顶点 $s$ ($1 \le s \le N$)，你需要计算满足 $1 \le u < v \le N$ 且 $u$ 可从 $v$ 到达（反之亦然）的顶点对 $(u, v)$ 的数量。

输入格式

第一行包含三个整数：$N$、$R$ 和 $M$。

第二行包含 $N - 1$ 个整数：$p[2], p[3], \dots, p[N]$，分别表示顶点 $2, 3, \dots, N$ 的父节点。

输出格式

输出 $N$ 行，每行一个整数：第 $s$ 行应包含选择顶点 $s$ 时所需的顶点对数量。

不建议使用 std::endl 输出换行符。为了获得更好的性能，请考虑使用 '\n'。

样例

样例输入 1

13 2 2
1 2 3 4 3 6 6 8 2 10 11 1

样例输出 1

16
4
15
55
66
36
66
55
66
45
55
66
66

说明 1

上图对应于 s = 2 的情况。

可到达的顶点对为：(1,13), (7,8), (7,9), (8,9)。

该列表不包含顶点对 (1,2)，因为顶点 2 已被感染。同样，顶点对 (1,5) 也不在列表中，因为 1 和 5 之间的路径上有三个感染顶点（2、3 和 4）。

样例输入 2

3 0 1
1 2

样例输出 2

1
1
1

数据范围

• $2 \le N \le 500\,000$
• $1 \le p[i] < i$ (对于每个 $2 \le i \le N$)
• $0 \le R \le N - 1$
• $0 \le M \le 2 \times R + 1$

子任务

1. (20 分) $N \le 300$
2. (14 分) $R = 0$
3. (15 分) $M = 2 \times R + 1$
4. (10 分) $M = 2 \times R - 1$
5. (16 分) $N \le 5\,000$
6. (25 分) 无附加限制。