Average of Levels in a Binary Tree

You are given a binary tree and your task is to compute the average value of the nodes on each level. The average for each level is computed using integer (floor) division. In other words, if the sum of the nodes in a level is \(S\) and there are \(N\) nodes in that level, then the average is \(\lfloor S/N \rfloor\).

The binary tree is provided in level order (breadth-first order) as a sequence of tokens separated by spaces. Each token is either an integer (representing a node value) or the string null (representing a missing node). Your task is to construct the binary tree from this input and then output the averages for each level as space-separated values.

Note: If the tree is empty, output nothing.

inputFormat

The input consists of a single line containing a sequence of tokens separated by spaces. Each token is either an integer or the string null. This sequence represents the level-order traversal of the binary tree. For example:

3 9 20 null null 15 7

represents the binary tree:

[ \begin{array}{c} 3 \ / \ 9 20 \ / \ 15 7 \end{array} ]

outputFormat

Print a single line with space-separated integers, where each integer represents the floor average of the values at that level of the binary tree.

For the above example, the output should be:

3 14 11

## sample

3 9 20 null null 15 7

3 14 11