Chạy trốn khỏi chuồng

Có $N$ ô cỏ nối nhau thành cây có gốc tại ô $1$. Mỗi cạnh có độ dài $l_i$. Bò chỉ di chuyển xa gốc (từ cha xuống con) và không chạy quá tổng quãng đường $L$.

Với mỗi ô $i$, đếm số ô có thể đến từ $i$ (bao gồm chính $i$) bằng cách di chuyển xa gốc với tổng quãng đường không quá $L$.

Dữ liệu vào

• Dòng $1$: Hai số nguyên $N$ và $L$ ($1\le N\le 200000$, $1\le L\le {10}^{18}$).
• Dòng $2$ đến $N$: Dòng $i$ gồm hai số nguyên $p_i$ và $l_i$ — cha của ô $i$ và độ dài cạnh ($1\le p_i<i$, $1\le l_i\le {10}^{12}$).

Dữ liệu ra

• $N$ dòng, dòng $i$ là số ô có thể đến từ ô $i$.

Ràng buộc

• $1\le N\le 200000$
• $1\le L\le {10}^{18}$
• $1\le l_i\le {10}^{12}$

Ví dụ