An excavation crew has mapped a sealed vault as a network of corridors branching outward, in the shape of a binary tree, from a single entrance chamber. At every junction along the way, restorers found a stone tablet stamped with a single digit, 0 or 1. Junctions with no further corridors are dead-end doors, each locked behind a dial that opens only to the correct passphrase. The passphrase for a given door is the binary number obtained by reading the stamped digits in order from the entrance chamber down to that door, with the entrance chamber's digit as the most significant bit.

You are given the full corridor map. Compute the sum, over every dead-end door, of its passphrase's numeric value.

Input format

The first line contains a single integer n, the number of junctions (numbered 0 to n-1; junction 0 is the entrance chamber). Each of the next n lines describes junction i (for i from 0 to n-1) with three integers bit_i left_i right_i, where bit_i is the digit (0 or 1) stamped at that junction, and left_i/right_i are the indices of its two corridor branches, or -1 if that branch does not exist.

Output format

Print a single integer: the sum of the passphrases of all dead-end doors (junctions with no branches).

Constraints

• 1 <= n <= 1000
• bit_i is 0 or 1
• The junctions form a single valid binary tree rooted at junction 0; every junction other than 0 is reachable from exactly one other junction, and there are no cycles.
• The total sum is guaranteed to fit within a signed 64-bit integer.

7
1 1 2
0 3 4
1 5 6
0 -1 -1
1 -1 -1
0 -1 -1
1 -1 -1

22

1
0 -1 -1

0