世界巡回赛决赛

题目描述

编程竞赛「世界巡回赛决赛（World Tour Finals）」正在进行，共有 $N$ 名选手参加，比赛时间已经过去了一半。 本场比赛共有 $M$ 道题，第 $i$ 道题的分值 $A_i$ 是 $500$ 到 $2500$ 之间（含端点）的 $100$ 的倍数。

对于每个 $i = 1, \ldots, N$，给定一个表示选手 $i$ 已解决问题的字符串 $S_i$。 $S_i$ 是长度为 $M$、由 o 和 x 组成的字符串，其中第 $j$ 个字符为 o 表示选手 $i$ 已经解决了第 $j$ 题，为 x 表示尚未解决。 这里，没有选手已经解决了所有题目。

选手 $i$ 的总分定义为已解决问题分值之和再加上 $i$ 分的奖励分。

对于每个 $i = 1, \ldots, N$，回答下面的问题：

选手 $i$ 至少还需要解决多少道尚未解决的题目，才能超过其他所有选手当前的总分？

注意：根据本题的条件与约束可以证明，选手 $i$ 通过解决所有题目一定能超过其他所有选手当前的总分，因此答案总是存在。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出 $N$ 行。第 $i$ 行输出选手 $i$ 的答案。

样例

3 4
1000 500 700 2000
xxxo
ooxx
oxox

0
1
1

比赛时间过半时各选手的总分为：选手 $1$ 为 $2001$ 分，选手 $2$ 为 $1502$ 分，选手 $3$ 为 $1703$ 分。

选手 $1$ 不需要再解决任何题目，其总分就已经超过了其他所有选手。

例如选手 $2$ 可以解决第 $4$ 题，使总分达到 $3502$ 分，从而超过其他所有选手的总分。

例如选手 $3$ 也可以解决第 $4$ 题，使总分达到 $3703$ 分，从而超过其他所有选手的总分。

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

1
1
1
1
0

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

7
6
5
4
3
2
0

数据范围

• $2\leq N\leq 100$
• $1\leq M\leq 100$
• $500\leq A_i\leq 2500$
• $A_i$ 是 $100$ 的倍数。
• $S_i$ 是长度为 $M$、由 o 和 x 组成的字符串。
• $S_i$ 至少包含一个 x。
• 输入中的所有数值均为整数。