Level Order Traversal of a Binary Tree

You are given a binary tree. Your task is to perform a level order traversal (also known as breadth-first search), and output the values of its nodes level by level, from left to right.

The binary tree is provided as a list of tokens in level order where the token null represents a missing node. You need to reconstruct the tree from this input, traverse it level by level, and then print each level on a separate line. For example, if the tree is given as:

3 9 20 null null 15 7

Then the resulting level order traversal output will be:

3
9 20
15 7

In mathematical notation, if the tree has levels indexed by i (starting from 0), and the set of node values at level i is \(L_i\), the output should list \(L_0, L_1, L_2, \dots\) where each \(L_i\) is printed on its own line.

inputFormat

The input is provided via stdin as a single line containing space-separated tokens. Each token is either an integer representing a node's value or the string null indicating a missing node. The tokens represent the tree in level order. Note that if the first token is null, the tree is empty.

Example: 3 9 20 null null 15 7

outputFormat

Output the level order traversal of the binary tree to stdout. Each level should be printed on a new line, with the node values separated by a space.

For example, for the input 3 9 20 null null 15 7, the output should be:

3
9 20
15 7

## sample

1

1