007 - 998244353点

時間制限 1 秒 / メモリ制限 64 MB / 得点 400 / x 5 /


TLE
1sec
MLE
64MB
得点
400

問題

あなたは $N$ 人の人から、ゲームの順位付けをする係をやってくれと頼まれました。
ゲームは $N$ 人で行われ、$i$ $(1 \leq i \leq N)$ 番目の人には番号 $i$ がつけられています。
ゲームの得点計算は以下のように行われます。

    ゲームの得点計算には $N$ 人のゲームの結果と、長さ $L$ の非負整数からなる数列 $A=(a_1,a_2,\ldots,a_L)$ を用いる。$A$ の要素は全て相異なる。
    $N$ 人のゲームの結果は ox からなる文字列で与えられ、$i$ 番目の人の結果を表す文字列は $S_i$ で長さは $L$ である。

    $i$ 番目の人は、$(1 \leq j \leq L)$ を満たす全ての $j$ について $S_i$ の $j$ 文字目が o であった場合 $998244353^{\large a_j}$ の得点を得る。

$N$ 人の番号を合計得点の高い順に出力してください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $L$
$a_1$ $a_2$ $\ldots$ $a_L$
$S_1$
$S_2$
$\vdots$
$S_N$

出力

出力は $N$ 行からなる。
$i$ 行目には合計得点が $i$ 番目に高い人の番号を出力せよ。ただし、得点が同じ人が複数存在する場合は番号の小さい順に出力せよ。

制約

  • $1 \leq N \leq 10^5$
  • $1 \leq L \leq 10$
  • $1 \leq a_j \leq 10^9$
  • $A$ の要素は全て相異なる
  • $S_i$ は ox のみからなる長さ $L$ の文字列である

入出力例

入力例1

5 5
5 3 2 1 4
xxoxx
oxxxo
xoxox
xooox
oxxxo

出力例1

2
5
4
3
1

$1$ 番目の人の得点は $998244353^2 = 996491788296388609$ です。
$2$ 番目の人の得点は $998244353^5 + 998244353^4 = 991252534890123971942135454737326947142991874$ です。
$3$ 番目の人の得点は $998244353^3 + 998244353^1 = 994742300477741420226019330$ です。
$4$ 番目の人の得点は $998244353^3 + 998244353^2 + 998244353^1 = 994742301474233208522407939$ です。
$5$ 番目の人の得点は $998244353^5 + 998244353^4 = 991252534890123971942135454737326947142991874$ です。

$2$ 番目の人と $5$ 番目の人の得点は等しいので番号の小さい順に出力してください。


入力例2

5 3
10 3 9
ooo
ooo
ooo
ooo
ooo

出力例2

1
2
3
4
5

入力例3

15 10
603124134 779804187 373980902 982838151 6578324 638150707 936364479 553361707 182080546 710345261
oxxxooxoox
oooxxoxxoo
ooooxxoxxx
xoxoxxoxoo
ooxxoxxxxo
xxoxooxxxx
xoxoooooox
xxxxxooxxx
xxoooooxxx
oooxoooxxx
xoxooxxooo
oxoooxxxox
ooooooooxx
oxoooxxxox
ooooxxxxox

出力例3

4
13
7
3
9
11
15
12
14
10
8
2
5
1
6