Andy is addicted to Minecraft. One day, he decides to download a new mod to enhance his gaming experience. The mod adds a million types of ores into the game, numbered from to , and requires a subset of distinct ores to be chosen. The mod then provides two new crafting recipes:

- Combine one ore of each type in , and summon a Herobrine with power , where denotes the size of subset .
- Combine two Herobrines with powers and into a single Herobrine with power .

Note that ingredients are destroyed once they are combined in a recipe.

Andy has to mine for these ores. The mine currently consists of chambers labelled from to , and tunnels labelled from to . The -th chamber consists of ores which Andy can mine, . The -th tunnel connects chambers and (), with the outside being considered as chamber .

Andy decides to begin mining in chamber . Overhearing his plans, Josh decides to block the -th tunnel with bedrock. Andy's only chance to escape is to summon a Herobrine to break the bedrock. Therefore, Andy decides to collect all the ores from chambers reachable from chamber via unblocked tunnels, and to create a single Herobrine with the maximum possible power.

Mike would like to know the power of Andy's Herobrine, but as he is currently looting a village, he has no idea which chamber Andy is in. Therefore, he wants to know: for each value of between and , across all possible subsets , what is the maximum possible power of Andy's Herobrine? Note that may differ for different values of .

#### Constraints

for all

##### Subtask 1 [20%]

##### Subtask 2 [40%]

for all .

##### Subtask 3 [40%]

No additional constraints.

#### Input Specification

The first line contains one integer, .

The second line contains integers, .

The -th of the following lines contains one integer, , followed by integers, .

#### Output Specification

Output lines. The -th line should contain one integer, denoting the maximum possible power of Andy's Herobrine if .

#### Sample Input

```
6
0 1 2 2 3 3
4 1 1 2 2
3 1 2 3
2 2 3
2 1 3
4 1 2 3 4
3 1 3 4
```

#### Sample Output

```
15
9
8
2
4
3
```

#### Explanation

Suppose , so that the second tunnel which connects chambers and is blocked with bedrock. Then, Andy can reach all chambers except chamber .

In total, Andy can mine ores of type , ores of type , ores of type , and ores of type .

If he chooses , then he can create Herobrines of power using the first crafting recipe. Using the second crafting recipe, he can combine two Herobrines to form a Herobrine with power . Using the second crafting recipe again, he can combine the two remaining Herobrines to form a single Herobrine with power . It can be shown that this choice of and this sequence of crafting operations is optimal.

## Comments