Task

Given a binary tree represented as a flat adjacency list, find all root-to-leaf paths and return them as strings in the format "A->B->C". A leaf is a node with no children. Perform a depth-first traversal from the root (node 0), collecting node values along each path, and output all paths in sorted lexicographic order.

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 one path per line, formatted as "v1->v2->...->vk", with all paths sorted lexicographically.

Example

Input:

5
1 1 2
2 3 4
3 -1 -1
4 -1 -1
5 -1 -1

Output:

1->2->4
1->2->5
1->3

Scaffolding

Submit a Python file defining:

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

Receives the number of nodes and three parallel lists of node values, left-child indices, and right-child indices; returns a sorted list of root-to-leaf path strings.