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 . Little does he know, code copies from coder . In fact, coder also copies code from code . This continues to form a tree, up until coder , 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 .
Copying code takes time. Coder takes minutes to copy the code from coder . Coder will have a , as he does not copy code.
Coder has just written a new piece of code at time . AQT would like to know how long it will take for a coder to copy it. He wants to know for all coders .
Input Specification
The first line will contain the integer , the number of coders.
The next lines will each contain two integers, . Coder will have . All other coders will have .
Output Specification
Output integers on one line, the integer indicating the amount of minutes it takes for coder to copy the code.
Sample Input
5
0 0
1 2
1 100
2 3
4 1
Sample Output
0 2 100 5 6
Comments