[Solution] Just Kingdom solution codeforces | ICPC WF Moscow Invitational Contest

Just Kingdom solution codeforces

The Just Kingdom is ruled by a king and his nn lords, numbered 11 to nn. Each of the lords is a vassal of some overlord, who might be the king himself, or a different lord closer to the king. The king, and all his lords, are just and kind.

Each lord has certain needs, which can be expressed as a certain amount of money they need. However, if a lord, or the king, receives any money, they will first split it equally between all their vassals who still have unmet needs. Only if all the needs of all their vassals are met, they will take the money to fulfill their own needs. If there is any money left over, they will return the excess to their overlord (who follows the standard procedure for distributing money).

At the beginning of the year, the king receives a certain sum of tax money and proceeds to split it according to the rules above. If the amount of tax money is greater than the total needs of all the lords, the procedure guarantees everybody’s needs will be fulfilled, and the excess money will be left with the king. However, if there is not enough money, some lords will not have their needs met.

For each lord, determine the minimum amount of tax money the king has to receive so that this lord’s needs are met.

Just Kingdom solution codeforces

Input

The first line of the input contains the number of lords nn (0n31050≤n≤3⋅105). Each of the next nn lines describes one of the lords. The ii-th line contains two integers: oioi (0oi<i0≤oi<i) — the index of the overlord of the ii-th lord (with zero meaning the king is the overlord), and mimi (1mi1061≤mi≤106) — the amount of money the ii-th lord needs.

Just Kingdom solution codeforces

Output

Print nn integer numbers titi. The ii-th number should be the minimum integer amount of tax money the king has to receive for which the needs of the ii-th lord will be met.

Just Kingdom solution codeforces

Example

input

Copy
5
0 2
1 2
0 1
1 1
0 5

output

Copy
11
7
3
5
11


Just Kingdom solution codeforces

Note

In the sample input, if the king receives 55 units of tax money, he will split it equally between his vassals — the lords 1133, and 55, with each receiving 5353 of money.

Lord 11 will split the money equally between his vassals — 22 and 44, with each receiving 5656. Lord 55 will keep the money (having no vassals). Lord 33 will keep 11 unit of money, and give the remaining 2323 to the king. The king will then split the 2323 between the vassals with unmet needs — 11 and 55, passing 1313 to each. Lord 55 will keep the extra cash (now having a total of 22, still not enough to meet his needs). Lord 11 will split it equally between his vassals, and the extra 1616 will be enough to meet the needs of lord 44.