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 ~1~ to ~10^6~, and requires a subset ~X~ of distinct ores to be chosen. The mod then provides two new crafting recipes:

1. Combine one ore of each type in ~X~, and summon a Herobrine with power ~|X|~, where ~|X|~ denotes the size of subset ~X~.
2. Combine two Herobrines with powers ~A~ and ~B~ into a single Herobrine with power ~A + B~.

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

Andy has to mine for these ores. The mine currently consists of ~N~ chambers labelled from ~1~ to ~N~, and ~N~ tunnels labelled from ~1~ to ~N~. The ~i~-th chamber consists of ~M_i~ ores which Andy can mine, ~O_{i,1}, O_{i,2}, \dots, O_{i,M_i}~. The ~i~-th tunnel connects chambers ~P_i~ and ~i~ (~P_i < i~), with the outside being considered as chamber ~0~.

Andy decides to begin mining in chamber ~C~. Overhearing his plans, Josh decides to block the ~C~-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 ~C~ 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 ~C~ between ~1~ and ~N~, across all possible subsets ~X~, what is the maximum possible power of Andy's Herobrine? Note that ~X~ may differ for different values of ~C~.

Constraints

~1 \le N \le 10 ^ 6~

~0 \le M_i \le 2 \times 10 ^ 6~

~1 \le \sum\limits_{i=1}^{N} M_i \le 2 \times 10 ^ 6~

~1 \le O_{i,j} \le 10^6~

~0 \le P_i < i~ for all ~i~

Subtask 1 [20%]

~1 \le N \le 1000~

~1 \le M_i \le 2000~

~1 \le \sum\limits_{i=1}^{N} M_i \le 2000~

Subtask 2 [40%]

~P_i = i - 1~ for all ~i~.

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line contains one integer, ~N~.

The second line contains ~N~ integers, ~P_1, P_2, \dots, P_N~.

The ~i~-th of the following ~N~ lines contains one integer, ~M_i~, followed by ~M_i~ integers, ~O_{i,1}, O_{i, 2}, \dots, O_{i,M_i}~.

Output Specification

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

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 ~C = 2~, so that the second tunnel which connects chambers ~1~ and ~2~ is blocked with bedrock. Then, Andy can reach all chambers except chamber ~1~.

In total, Andy can mine ~4~ ores of type ~1~, ~3~ ores of type ~2~, ~5~ ores of type ~3~, and ~2~ ores of type ~4~.

If he chooses ~X = \{1, 2, 3\}~, then he can create ~3~ Herobrines of power ~3~ using the first crafting recipe. Using the second crafting recipe, he can combine two Herobrines to form a Herobrine with power ~3 + 3 = 6~. Using the second crafting recipe again, he can combine the two remaining Herobrines to form a single Herobrine with power ~3 + 6 = 9~. It can be shown that this choice of ~X~ and this sequence of crafting operations is optimal.