Task

Given a binary tree, serialize it to a BFS level-order string, deserialize that string back into a tree, and return the sum of all node values. Serialization uses space-separated values with -1 representing null nodes. Trailing -1 tokens are trimmed. Deserialization reconstructs the tree from the level-order representation.

Input

• Line 1: n — number of nodes
• Lines 2 to n+1: value left right — integer value, left child index (-1 if none), right child index (-1 if none); nodes are 0-indexed, root is node 0

Output

Print a single integer: the sum of all node values after the serialize-deserialize round-trip.

Example

Input:

3
1 1 2
2 -1 -1
3 -1 -1

Output:

6

Scaffolding

Submit a Python file defining:

def serialize_deserialize_sum(n: int, vals: list[int],
                               lefts: list[int], rights: list[int]) -> int:
    ...

Receives the number of nodes and parallel lists of node values, left-child indices, and right-child indices; returns the sum of all node values after a serialize-deserialize round-trip.