#411 Round-Robin Tree

Statement

Statement language

You are given a rooted tree with $N$ vertices. Vertex $1$ is the root.

For every non-leaf vertex $v$ , you may choose one linear ordering of the children of $v$ . The order is fixed before any ball is inserted and cannot be changed while the balls move.

Balls are inserted into the root one by one. Consider the $i$ -th ball that enters a vertex $v$ . If $v$ has $d_v$ children, the ball moves to the

((i-1) \bmod d_v)+1

-th child in the chosen order. A ball stops when it reaches a leaf.

Whenever a ball reaches a leaf $v$ , you gain $C_v$ points. The value $C_v$ may be negative.

For every $x=1,2,\cdots,X$ , find the maximum total score obtainable after inserting $x$ balls into the root. The child orderings may be chosen differently for different values of $x$ .

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print $X$ integers $A_1,A_2,\cdots,A_X$ on one line, separated by spaces.

Constraints

$1 \le T \le 200\,000$ .
$1 \le N \le 200\,000$ .
$1 \leq X$ .

Subtasks

#	Score	Constraints
1	12	$N \le 8$ . $X \le 8$ .
2	8	Every non-leaf vertex has exactly one child.
3	12	Every vertex except vertex $1$ is a leaf.

Samples

Input

2
5
2
3
4
5
5 1 0 3
6
2
3
4
5
6
7
0 0 10 0 6 5

Output

5 8 9 14 17
10 16 21 21 31 37

For each value of $x$ , choose the child orderings and move every ball according to the rule. Selecting an ordering with the highest total score gives the printed values.