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

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

1. 其他城市 Y_i 只能选自以当前城市 X_i 为根的子树中。

2. 其他城市 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 城市的居民，通过乘坐直达航班，最多可以到达多少个不同的城市旅行。

样例 1 解释

1 号点所在的子树中，到 1 号点距离不超过 10 的点有 3 4，因此 1 号点可以通过航往返于 1-3 和 1-4 之间，因此 1 号城市的居民可以在 1 3 4 三个城市旅行。

同理， 2 号城市的居民可以在 2 号城市旅行。

3 号城市的居民可以在 3 4 5 三个城市旅行。

4 号城市的居民可以在 4 号城市旅行。

5 号城市的居民可以在 5 号城市旅行。

数据范围

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

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

• 1 \leq N \leq 2 \times 10^5，1 \leq L \leq 10^{18}。
• 1 \leq F_i \lt i，1 \leq P_i \leq 10^{12}。

月赛树树上差分倍增