Bajtek received the latest computer game, Byte Defence 4, from his parents for the holidays. As an avid gamer, he immediately inserted the disc into the CD drive and started playing. He discovered that in the game, he controls a character called the Bajtonator, who must gain experience, complete tasks, and acquire increasingly better equipment. Bajtek also discovered that there are $n$ special arenas located on the game map where he can obtain very valuable items. Unfortunately, to enter an arena, one must possess a special pass dedicated to that arena. Bajtek decided to take a closer look at the system of arenas and passes.
An arena is a place of combat. If a player has a pass for it, they can go there and face the monster waiting inside. Entering an arena does not cause the loss of the pass. The monster in the arena respawns when the player leaves; therefore, one can visit each arena multiple times, using the same pass each time. When a player defeats the monster in the arena, they receive—in addition to rarely encountered items—a new pass.
The new pass is drawn from a special pool of passes for that arena. The pool of passes for each arena is public and known to Bajtek. After a victory in an arena, a pass is drawn from its pool, and a copy of it is given to the player. No pass pool ever changes, nor does anything disappear from it. Thus, it is possible that after a certain number of victories, a player will possess many copies of one pass.
Unfortunately, fighting the monsters is not easy. After browsing online guides, Bajtek learned that as the arena numbers increase, their difficulty increases. He concluded that there must be a constant $k$ such that he is able to easily defeat monsters in arenas with numbers less than or equal to $k$, and he is certainly unable to defeat monsters in arenas with numbers greater than $k$.
Bajtek, encouraged by the possibility of obtaining exclusive items, decided to start fighting in the arenas. However, he realized that he did not possess any passes—he would have to buy one with real money. Somewhat disappointed by the game's system, he decided not to give up and buy one pass. He did not know which one, though—after all, he would like to use it to unlock access to other arenas.
"If I buy only a pass for arena $A$ and thanks to it I am absolutely certain that I will eventually be able to achieve victory in arena $B$, then it is not such a bad purchase," the boy thought.
He was then faced with the question: for a fixed value of $k$, how many ordered pairs of arenas $(A, B)$ exist, where $A \neq B$, such that by buying a pass for arena $A$, Bajtek can be absolutely certain that with his optimal strategy, he will eventually be able to enter arena $B$ and achieve victory there, regardless of which passes he receives for his victories? Formally, for a fixed pair of arenas $(A, B)$, there must exist such a strategy for choosing arenas to fight in* and such a finite constant $M$ that the player, by choosing arenas according to the strategy, is able to force a victory in arena $B$ after at most $M$ won battles.
Determining the number of arena pairs turned out to be too difficult for him, so he turned to you for help. Help him and determine this number for every possible value of $k$.
Input
The first line of input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$), representing the number of arenas (and also the number of types of passes).
The next $n$ lines contain descriptions of the pass pools; the $i$-th line starts with one integer $\ell_i$ ($1 \le \ell_i$), representing the number of passes in the $i$-th pool. Then, in the same line, there is a sequence of $\ell_i$ integers representing the numbers of the arenas to which the passes from the $i$-th pool grant access. Arenas are indexed with integers from $1$ to $n$.
The sum of $\ell_i$ values in one file will not exceed $5 \cdot 10^5$.
Output
The single line of output should contain $n$ integers—the $k$-th integer represents the number of ordered pairs of arenas $(A, B)$ such that $A \neq B$ and after buying a pass for arena $A$, the player can be certain that they will eventually be able to achieve victory in arena $B$, assuming they are only able to win battles in arenas with indices not exceeding $k$.
*The strategy is formally a function from the game state to a move, but one can also think of it as a decision tree saying which arena we should play in now, depending on which passes we currently possess.
Examples
Input 1
9 2 2 3 1 1 1 2 1 5 3 5 8 9 1 5 2 6 4 2 5 9 3 5 8 5
Output 1
0 1 4 4 5 6 7 7 7
Note
If $k = 9$ (meaning the boy is able to win in every arena) and Bajtek buys a pass for the first arena ($A = 1$) and wins there, he will receive a pass for the second or third arena. If he receives a pass for the third arena, he can face the opponents there and be certain that he will receive a pass for the second arena as a reward. The pair of arenas $(1, 2)$ is therefore correct and should be counted in the result.
If $k = 2$, then after buying a pass for the first arena ($A = 1$), Bajtek might receive a pass for the third arena, where unfortunately he will not be able to cope. For this reason, no pair of arenas where ($A = 1$) should be counted in the result for $k = 2$.
If $k \ge 7$ and Bajtek buys a pass for the seventh arena ($A = 7$), then regardless of how many times he wins there, he might constantly receive only passes for the fourth arena or only for the sixth arena. Therefore, neither the pair $(7, 4)$ nor the pair $(7, 6)$ should be included in the result for any value of $k$. However, regardless of whether he possesses a pass for the fourth or sixth arena, Bajtek can go to that arena and obtain a pass for the fifth arena there. The pair $(7, 5)$ should therefore be included in the result.
If $k < 7$ and Bajtek buys a pass for the seventh arena, he will unfortunately get stuck immediately, as the monster waiting there will be far too strong for him.
All correct arena pairs for $k = 9$ are: $(1, 2), (2, 1), (3, 1), (3, 2), (4, 5), (6, 5)$ and $(7, 5)$.