Đã tới giờ cho uống nước ở nông trại của nông dân John (FJ), nhưng các con bò lại đang bỏ chạy!

FJ muốn tập trung chúng lại, và ông ta cần sự giúp đỡ của bạn. Nông trại của FJ là một dãy gồm có \(N\) \((1 \leq N \leq 200000)\) bãi cỏ được đánh số từ \(1 \ldots N\) và được nối bằn \(N-1\) con đường hai chiều. Chuồng bò nằm ở bãi cỏ thứ nhất, và từ bãi thứ nhất, ta có thể đi đến tất cả các bãi cỏ còn lại. Những con bò của FJ đang ở bãi cỏ của chúng vào sáng nay, nhưng không ai biết chúng đã đi đâu cho tới bây giờ. FJ biết rằng những con bò chỉ muốn chạy xa khỏi nhà chứa, nhưng cũng cũng rất lười nên không thể chạy một đoạn đường có độ dài lớn hơn \(L\) (theo hướng xa nhà chuồng). Với mỗi bãi cỏ, FJ muốn biết có bao nhiêu bãi cỏ mà những con bò bắt đầu tại bãi cỏ đó có thể dừng chân.

Lưu ý: Số dạng 64 bit (trong Pascal là int64, trong C/C++ là long long, và trong Java là long) cần dùng để lưu các khoảng cách.

Input

• Dòng đầu tiên ghi hai số nguyên \(N, L\) \((1 \leq N \leq 200000, \ 1 \leq L \leq 10^{18})\)
• \(N-1\) dòng tiếp theo, dòng thứ \(i\) ghi hai số \(p_i,l_i\) với \(p_i\) là bãi cỏ đầu tiên trên đường đi ngắn nhất từ \(i+1\) đến nhà chứa, \(l_i\) là khoảng cách con đường đó \((1 \leq p_i < i+1, \ 1 \leq l_i \leq 10^{12})\)

Output

• gồm \(N\) dòng, dòng thứ là số lượng bãi cỏ có thể đi tới được từ bằng cách rời xa nhà chứa (bãi cỏ 1) với độ dài không quá \(L\).

Example

4 5
1 4
2 3
1 5

3
2
1
1