Problem Statement

There are $N$ players. Initially, person $i$ has a string $S_i$. Every player knows all of the strings held by everyone.

They play a game consisting of the following two stages.

Stage 1

• Each player declares a positive integer of their choice
• Let $K$ be the smallest of the declared positive integers

Stage 2

• Each player $i$ performs the following operation exactly $K$ times
  • Choose two characters at different positions in the string $S_i$ they hold, and swap them

Among the strings finally produced, all people who hold the lexicographically smallest string win. Each winner gets $N+1-X$ points, where $X$ is the number of winners.

Find everyone's score when all players follow a strategy that maximizes their own score.

Constraints

• $N \ge 2$
• $2 \le |S_i| \le 10^5$
• $\sum |S_i| \le 2 \times 10^5$
• $S_i$ consists only of lowercase English letters

Input

The input is given from standard input in the following format.

$N$
$S_1$
$\vdots$
$S_N$

Output

Print $N$ lines. The $i$-th line should contain the score of player $i$ when all players follow a strategy that maximizes their own score.

Sample

3
ac
re
wa

0
0
3

4
abc
cba
bac
abc

0
3
3
0

5
apple
banana
cabbage
dragonfruit
egg

0
0
5
0
0