問題
あなたは $N$ 人の人から、ゲームの順位付けをする係をやってくれと頼まれました。
ゲームは $N$ 人で行われ、$i$ $(1 \leq i \leq N)$ 番目の人には番号 $i$ がつけられています。
ゲームの得点計算は以下のように行われます。
ゲームの得点計算には $N$ 人のゲームの結果と、長さ $L$ の非負整数からなる数列 $A=(a_1,a_2,\ldots,a_L)$ を用いる。$A$ の要素は全て相異なる。
$N$ 人のゲームの結果は o と x からなる文字列で与えられ、$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$ は
oとxのみからなる長さ $L$ の文字列である
入出力例
入力例１
5 5 5 3 2 1 4 xxoxx oxxxo xoxox xooox oxxxo
出力例１
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$ 番目の人の得点は等しいので番号の小さい順に出力してください。
入力例２
5 3 10 3 9 ooo ooo ooo ooo ooo
出力例２
1 2 3 4 5
入力例３
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
出力例３
4 13 7 3 9 11 15 12 14 10 8 2 5 1 6