AQT is trying to get better at programming. However, he can't, despite his best efforts, and as such has resorted to copying code. He wishes to copy code from coder ~a_N~. Little does he know, code ~a_N~ copies from coder ~a_{a_N}~. In fact, coder ~a_{a_N}~ also copies code from code ~a_{a_{a_N}}~. This continues to form a tree, up until coder ~1~, who writes his own code. AQT is a leaf node, that is, no one copies code from him. There are many other leaf nodes, such as BQT, and CQT.

AQT is guaranteed to be coder ~N~.

Copying code takes time. Coder ~i~ takes ~k_i~ minutes to copy the code from coder ~a_i~. Coder ~1~ will have a ~k_i = 0~, as he does not copy code.

Coder ~1~ has just written a new piece of code at time ~0~. AQT would like to know how long it will take for a coder ~i~ to copy it. He wants to know for all coders ~i~ ~(1 \le i \le N)~.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~, the number of coders.

The next ~N~ lines will each contain two integers, ~a_i, k_i~ ~(0 \le a_i < i, 0 \le k_i \le 100)~. Coder ~1~ will have ~a_1 = 0, k_1 = 0~. All other coders will have ~a_i > 0, k_i > 0~.

Output Specification

Output ~N~ integers on one line, the ~i^{th}~ integer indicating the amount of minutes it takes for coder ~i~ to copy the code.

Sample Input

5
0 0
1 2
1 100
2 3
4 1

Sample Output

0 2 100 5 6