Subtree Sum in a Binary Tree

You are given a binary tree represented by a list of node information. Each node is described by four integers: the node's identifier u, its value v, the identifier of its left child l (or -1 if there is no left child), and the identifier of its right child r (or -1 if there is no right child). The tree is rooted at the node with identifier 1.

Your task is to compute the subtree sum for each node. The subtree sum of a node is defined as

$$S = v + S_L + S_R,$$

where:

• v is the value of the current node,
• S_L is the subtree sum of its left child (0 if none),
• S_R is the subtree sum of its right child (0 if none).

The results must be output in level order (i.e. breadth-first order) of the nodes.

inputFormat

The input is given via stdin. The first line contains an integer N, the number of nodes in the tree. Each of the next N lines contains four space-separated integers u v l r representing:

• u – the identifier of the node,
• v – the value of the node,
• l – the identifier of the left child (or -1 if there is no left child),
• r – the identifier of the right child (or -1 if there is no right child).

outputFormat

Output the subtree sum of each node in level order via stdout, with each sum printed on a new line.

## sample

1
1 3 -1 -1

3

</p>