该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

dXqwq 是个富可敌国的女孩子。

她的公司有 n 位员工，编号为 1∼n，她既是老板也是编号为 1 的员工，她的上司用 0 表示；而剩余的员工都有一个比其编号更小的直接上司 pi。

保证对于每位员工，其恰好有偶数个直接下属。

现在公司在表决一起提案，第 i 位员工的意见是 ai，其中 0 代表不支持，1 代表支持。

提案的审核方式是，对于 1 号员工，先询问其所有直接下属是否支持提案，如果支持者较多或不支持者较多就采纳多数人的反馈，否则使用自己的意见作为反馈；而所有下属的反馈同样按照此规则计算。

不难发现，此时一些员工的意见没有任何意义，一个员工的意见有意义当且仅当如果他的意见改变，他的反馈也会改变。

好在 dXqwq 可以贿赂一些员工：她可以花费 bi 的代价使第 i 位员工的意见改变。

dXqwq 想要对 x=1∼n 求出，如果要让第 x 位员工的意见有意义，她至少要花费的代价。

Input Format

从文件 vote.in 中读入数据。

第一行输入一个整数 n。

接下来 n 行，每行输入三个整数 pi,ai,bi。

Output Format

输出到文件 vote.out 中。

输出 n 行，每行包含一个整数，第 i 行输出使 i 的意见有意义的最小代价。

5
0 0 3
1 1 6
1 0 5
3 1 7
3 1 9

6
0
7
0
0

Hint

样例

Input 1

	5
0 0 3
1 1 6
1 0 5
3 1 7
3 1 9
	

		
	

Output 1

	6
0
7
0
0
	

		
	

Input 2

	见下发的 vote2.in。
该样例满足测试点 3 的性质。
	

		
	

Output 2

	见下发的 vote2.ans。
该样例满足测试点 3 的性质。
	

		
	

Input 3

	见下发的 vote3.in。
该样例满足测试点 8 的性质。
	

		
	

Output 3

	见下发的 vote3.ans。
该样例满足测试点 8 的性质。
	

		
	

数据范围

本题共 10 个测试点，全部测试点满足 3≤n≤105，min(i−1,0)≤pi<i，0≤ai≤1，0≤bi≤109。

样例解释

对于样例，我们如果什么都不做，表决过程如下：

• 5 号员工的反馈为同意。
• 4 号员工的反馈为同意。
• 3 号员工的两个直接下属都反馈同意，所以反馈同意。
• 2 号员工的反馈为同意。
• 1 号员工的两个直接下属都反馈同意，所以反馈同意。

对于 x=3 的情况，我们贿赂 4 号员工，使其意见变为不同意。

• 5 号员工的反馈为同意。
• 4 号员工的反馈为不同意。
• 3 号员工的两个直接下属意见不同，所以反馈自身意见不同意。
• 2 号员工的反馈为同意。
• 1 号员工的两个直接下属意见不同，所以反馈自身意见不同意。

此时不难发现如果 3 号员工的意见改变，其反馈的结果也会改变。