B - Test Ranking Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君のクラスでは期末テストが行われました。このテストには N 人の生徒が参加し、全部で M 問の問題が出題されました。

j 番目の問題 (1 \leq j \leq M) には配点 P_j が設定されています。各生徒の合計点は、その生徒が正解した問題の配点の総和です（不正解の問題の配点は加算されません）。

i 番目の生徒 (1 \leq i \leq N) の解答結果は文字列 S_i で表されます。S_i は長さ M の文字列であり、j 文字目が o ならば j 番目の問題に正解したことを、x ならば不正解であったことを意味します。

各生徒の合計点をもとに順位を求めてください。ある生徒の順位は「その生徒より合計点が真に高い生徒の人数 + 1」で定義されます。したがって、同じ合計点の生徒が複数いる場合は同じ順位となります。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • N \times M \leq 5 \times 10^6
  • 1 \leq P_j \leq 1000 (1 \leq j \leq M)
  • S_i は長さ M の文字列であり、o と x のみからなる (1 \leq i \leq N)
  • N, M, P_j はすべて整数

入力

N M
P_1 P_2 \ldots P_M
S_1
S_2
\vdots
S_N
  • 1 行目には、生徒の人数を表す整数 N と問題数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各問題の配点を表す整数 P_1, P_2, \ldots, P_M が、スペース区切りで与えられる。
  • (2+i) 行目 (1 \leq i \leq N) には、i 番目の生徒の解答結果を表す文字列 S_i が与えられる。

出力

N 行出力してください。i 行目 (1 \leq i \leq N) には、i 番目の生徒の順位を出力してください。

入力例 1

5 3
100 200 300
oxo
ooo
xxo
oox
xxx

出力例 1

2
1
3
3
5

入力例 2

4 4
10 20 30 40
ooxx
xxoo
oxox
xoxo

出力例 2

4
1
3
2

入力例 3

10 5
50 30 20 80 10
ooooo
oxxxx
xoxox
ooxoo
xxxxx
oxoxo
oooox
xxoox
xooox
oxxxo

出力例 3

1
9
5
3
10
7
2
6
4
8

入力例 4

20 8
15 25 35 45 55 65 75 85
oooooooo
xxxxxxxx
oxoxoxox
xoxoxoxo
ooooxxxx
xxxxoooo
oxxooxxo
xooxxoox
ooxxooxx
xxooxxoo
oxooxoxo
xoxxoxox
oxxxoooo
xoooxoox
oxooxxox
xoxxoxxo
oooxoxox
xxxoxxoo
oxoxooxx
xoxooxoo

出力例 4

1
20
13
8
19
4
11
11
17
7
5
18
2
5
14
16
9
9
14
3

入力例 5

1 1
1000
o

出力例 5

1

Score : 300 pts

Problem Statement

A final exam was held in Takahashi's class. N students participated in this exam, and a total of M problems were given.

The j-th problem (1 \leq j \leq M) has a score of P_j. Each student's total score is the sum of the scores of the problems that the student answered correctly (scores of incorrectly answered problems are not added).

The answer result of the i-th student (1 \leq i \leq N) is represented by a string S_i. S_i is a string of length M, where the j-th character being o means the student answered the j-th problem correctly, and x means the student answered it incorrectly.

Determine the rank of each student based on their total scores. The rank of a student is defined as "the number of students whose total score is strictly higher than that student's + 1". Therefore, students with the same total score will have the same rank.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • N \times M \leq 5 \times 10^6
  • 1 \leq P_j \leq 1000 (1 \leq j \leq M)
  • S_i is a string of length M consisting only of o and x (1 \leq i \leq N)
  • N, M, P_j are all integers

Input

N M
P_1 P_2 \ldots P_M
S_1
S_2
\vdots
S_N
  • The first line contains an integer N representing the number of students and an integer M representing the number of problems, separated by a space.
  • The second line contains integers P_1, P_2, \ldots, P_M representing the score of each problem, separated by spaces.
  • The (2+i)-th line (1 \leq i \leq N) contains the string S_i representing the answer result of the i-th student.

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the rank of the i-th student.

Sample Input 1

5 3
100 200 300
oxo
ooo
xxo
oox
xxx

Sample Output 1

2
1
3
3
5

Sample Input 2

4 4
10 20 30 40
ooxx
xxoo
oxox
xoxo

Sample Output 2

4
1
3
2

Sample Input 3

10 5
50 30 20 80 10
ooooo
oxxxx
xoxox
ooxoo
xxxxx
oxoxo
oooox
xxoox
xooox
oxxxo

Sample Output 3

1
9
5
3
10
7
2
6
4
8

Sample Input 4

20 8
15 25 35 45 55 65 75 85
oooooooo
xxxxxxxx
oxoxoxox
xoxoxoxo
ooooxxxx
xxxxoooo
oxxooxxo
xooxxoox
ooxxooxx
xxooxxoo
oxooxoxo
xoxxoxox
oxxxoooo
xoooxoox
oxooxxox
xoxxoxxo
oooxoxox
xxxoxxoo
oxoxooxx
xoxooxoo

Sample Output 4

1
20
13
8
19
4
11
11
17
7
5
18
2
5
14
16
9
9
14
3

Sample Input 5

1 1
1000
o

Sample Output 5

1