Decrypt Binary Tree Traversals

You are given a binary tree with n nodes. The tree is represented as a list of nodes, where each node is described by three values: value, left, and right. The left and right values represent the indices of the left and right children in the list, respectively. If a child is missing, the value will be given as None.

The root of the tree is always the first node in the list (index 0). Your task is to decrypt the binary tree by concatenating the results of the following tree traversals:

• Pre-order: \(\text{Root, Left, Right}\)
• In-order: \(\text{Left, Root, Right}\)
• Post-order: \(\text{Left, Right, Root}\)

Output the concatenated result as a sequence of integers, separated by a single space.

inputFormat

The first line contains an integer n representing the number of nodes in the tree. If n is 0, the tree is empty.

The next n lines each contain three tokens: value left right. Here:

• value is an integer representing the node's value.
• left is either an integer representing the index of the left child or None if there is no left child.
• right is either an integer representing the index of the right child or None if there is no right child.

Indices are zero-based, and the root is at index 0.

outputFormat

Output a single line containing the concatenated traversal result. That is, print the pre-order, followed by the in-order, followed by the post-order traversal sequences, with each integer separated by a single space.

## sample

5
1 1 2
2 None None
3 3 4
4 None None
5 None None

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