Đã 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 \le N \le 200000~) bãi cỏ được đánh số từ ~1 \dots N~ và được nối bằng ~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 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à chứa). 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 C/C++ là long long) cần dùng để lưu các khoảng cách.

Yêu cầu: Với mỗi bãi cỏ ~i~, hãy tính số lượng bãi cỏ mà bò có thể đi tới được từ ~i~ bằng cách rời xa nhà chứa (bãi cỏ 1) với tổng độ dài không quá ~L~.

Input

• Dòng đầu tiên ghi hai số nguyên ~N, L~ (~1 \le N \le 200000, 1 \le L \le 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 \le p_i < i+1, 1 \le l_i \le 10^{12}~).

Output

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