N-ary Tree Level Order Traversal

You are given an N-ary tree. Your task is to perform a level order traversal on the tree and print each level's node values on a separate line. Within each level, the node values must appear in the order they are encountered.

The tree is serialized using a special format explained below.

If the tree is empty, print nothing.

Note: A level order traversal visits nodes level by level from top to bottom. The first level is the root. For each node, its children (if any) are processed from left to right.

The input tree follows this format using a special marker:

• If the tree is empty, the input is the string null.
• Otherwise, the tree is serialized in level order. For each node, its integer value is given, followed by the values of its children. A '#' token marks the end of the children list for a node.

For example, consider the following trees:

• A single node tree: 1 #
• A tree with root 1 and children 2, 3, 4: 1 2 3 4 # # # #
• A tree where the root 1 has children 3, 2, 4 and node 3 has children 5,6: 1 3 2 4 # 5 6 # # # #
• A tree where the root 1 has children 2, 3, 4; node 2 has child 5; node 3 has child 6 which in turn has child 7: 1 2 3 4 # 5 # 6 # # 7 # #

Output the level order traversal where each level is printed on a new line with its node values separated by a single space.

Mathematically, if \(L_i\) denotes the set of nodes at level \(i\), output each \(L_i\) in order, for \(i \ge 1\).

inputFormat

The input consists of a single line containing the serialized N-ary tree. Tokens are separated by spaces. If the tree is empty, the line contains the string "null". Otherwise, the first token is the root's value followed by its children values and a '#' marker to denote the end of children for that node. This pattern repeats level by level.

outputFormat

Output the level order traversal of the tree. Each level's node values should be printed on a separate line, with values separated by a single space. If the tree is empty, output nothing.## sample

null