Convert Ternary Tree to Circular Doubly Linked List

You are given a tree in which each node has up to three children: left, middle, and right. The tree is provided in level order, where missing nodes are represented by the string null. Your task is to convert this tree into a circular doubly linked list (DLL) using level order traversal. In the resulting DLL, each node should contain only the value, and the list must be circular (i.e. the next pointer of the last node should point to the head, and the previous pointer of the head should point to the last node).

Note: If the input tree is empty, output nothing. The conversion should proceed in the order of nodes as they appear in a level order traversal.

The level order list of nodes is processed as follows:

Let \(T = [a_1, a_2, \ldots, a_n]\) where a token null indicates a missing node. Create the root node with \(a_1\) if it is not null, and then assign subsequent children for each node in the order: left, then middle, then right.

The final output should be a space‐separated list of the node values in the order they appear in the circular DLL, starting at the head.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer n indicating the number of tokens in the level order representation of the tree. If n is 0, the tree is empty.
• The second line contains n tokens separated by spaces. Each token is either an integer or the string null (representing a missing node).

For example:

4
1 2 3 4

outputFormat

Output the values of the nodes in the constructed circular doubly linked list. The values should be printed in a single line separated by a single space. If the tree is empty, output nothing.

## sample

11
10 12 15 20 25 30 36 null null null 40

10 12 15 20 25 30 36 40