题目描述

A国有 $N$ 个城市，城市编号 $1 \sim N$。$N$ 个城市之间通过 $N − 1$ 条高速公路连成了一棵树，其中 $1$ 号城市是这棵树的根。

现每个城市准备开通若干条直达航班。为了节约资源，民航局规定，对于任意的城市 $X_i$ 只能开通往返于当前城市和满足如下条件的其他城市 $Y_i$ 之间的直达航班：

• 其他城市 $Y_i$ 只能选自以当前城市 $X_i$ 为根的子树中。
• 其他城市 $Y_i$ 到当前城市 $X_i$ 高速公路的距离不超过 $L$。

请你编程求解出，当这些直达航班都开通之后，每个城市的居民，通过乘坐直达航班，最多可以到达多少个不同的城市旅行。

特别的，每个城市的居民都可以在自己所在的城市旅行，因此计算每个城市的居民可旅行的城市时，请加上其所在的城市。

输入格式

第 $1$ 行输入两个整数 $N$ 和 $L$。

第 $2$ 到第 $N$ 行，每行两个整数，第 $i$ 行的整数 $F_i, P_i$ 表示 $i$ 号城市在树上的父元素为 $F_i$ 号城市，$i$ 与 $F_i$ 之间高速公路的距离为 $P_i$。

输出格式

输出 $N$ 行，每行一个整数，第 $i$ 行的整数表示编号为 $i$ 城市的居民，通过乘坐直达航班，最多可以到达多少个不同的城市旅行。

样例

输入

5 10
1 12
1 2
3 8
3 9

输出

3
1
3
1
1

数据范围

对于 $30\%$ 的数据，满足 $1 \le N \le 5000$，$1 \le L \le 3000$。

对于全部的测试点，保证：

• $1 \le N \le 2 \times 10^5$，$1 \le L \le 10^{18}$。
• $1 \le F_i < i$，$1 \le P_i \le 10^{12}$。