正义王国由一位国王和他的 $$$n$$$ 领主统治,编号为 $$$1$$$ 到 $$$n$$$。每个领主都是某个领主的封臣,这个领主可能是国王本人,也可能是与国王关系更近的其他领主。国王和他的所有领主都是公正而仁慈的。
每个领主都有一定的需求,可以表现为他们需要一定数量的金钱。然而,如果领主或国王收到任何金钱,他们将首先将其平均分配给所有仍有未满足需求的封臣。只有满足所有封臣的所有需求,他们才会拿这些钱来满足自己的需要。如果还有剩余的钱,他们会将多余的部分返还给他们的领主(领主遵循分配金钱的标准程序)。
年初,国王收到一定数额的税款,并按照上述规则进行分割。如果税收数额大于所有领主的总需求,程序保证每个人的需求都得到满足,多余的钱将留给国王。然而,如果没有足够的钱,有些领主的需求就无法得到满足。
对于每个领主,确定国王必须收到的最低税款金额,以满足该领主的需求。
输入
输入的第一行包含领主的数量 $$$n$$$ ($$$0 \le n \le 3 \cdot 10^5$$$)。接下来的每一行 $$$n$$$ 描述了一位领主。第 $$$i$$$ 行包含两个整数:$$$o_i$$$ ($$$0 \le o_i < i$$$) — 第 $$$i$$$ 领主的领主索引(零表示国王是领主),以及 $$$m_i$$$ ($$$1 \le m_i \le 10^6$$$) — 领主的金额$$$i$$$-th 领主需要。
输出
打印 $$$n$$$ 整数 $$$t_i$$$。第 $$$i$$$ 数字应该是国王必须收到的、满足第 $$$i$$$ 领主需求的最小整数税款。
示例
输入 #1
5 0 2 1 2 0 1 1 1 0 5
输出 #1
11 7 3 5 11
注意
在示例输入中,如果国王收到 $$$5$$$ 单位的税金,他会将其平分给他的封臣——领主 $$$1$$$、$$$3$$$ 和 $$$5$$$,每个领主收到 $$$\frac{5}{3}$$$ 的钱。
领主$$$1$$$将在他的封臣之间平分金钱——$$$2$$$和$$$4$$$,每个封臣收到$$$\frac{5}{6}$$$。领主 $$$5$$$ 将保留这笔钱(没有封臣)。领主$$$3$$$将保留$$$1$$$单位的货币,并将剩余的$$$\frac{2}{3}$$$交给国王。然后,国王将在未满足需求的封臣之间分配 $$$\frac{2}{3}$$$ — $$$1$$$ 和 $$$5$$$,将 $$$\frac{1}{3}$$$ 传递给每个封臣。主$$$5$$$将保留额外的现金(现在总共$$$2$$$,仍然不足以满足他的需要)。领主$$$1$$$将平分给他的封臣,额外的$$$\frac{1}{6}$$$足以满足领主$$$4$$$的需要。