题目描述

有 $N$ 名选手参加的编程比赛世界巡回赛决赛正在进行中,比赛时间已经过半。
这场比赛共有 $M$ 道题目,第 $i$ 题的分值 $A_i$ 是 $500$ 到 $2500$ 之间的 $100$ 的倍数。
对于每个$i=1,\ldots,N$,给出一个字符串 $S_i$ 表示选手 $i$ 已经解决了哪些题目。
$S_i$ 是一个长度为 $M$ 的由 $o$ 和 $x$ 组成的字符串,其中 $S_i$ 的第 $j$ 个字符为 $o$ 表示选手 $i$ 已经解决了第$j$ 题,为 $x$ 表示还没有解决。
这里,没有选手解决了所有题目。
选手 $i$ 的总分计算为其解决的题目分值之和,再加上 $i$ 分的奖励分。
现在,对于每个 $i=1,\ldots,N$,请回答以下问题:
选手 $i$ 至少要再解决多少道还未解决的题目,才能让选手 $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

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

样例1解释

在比赛时间过半时,各选手的总分为:选手$1$是$2001$分,选手$2$是$1502$分,选手$3$是$1703$分。
选手 $1$ 已经领先于其他所有选手的总分,不需要再解决任何题目。
选手 $2$ 可以解决第 $4$ 题,总分将达到 $3502$ 分,超过其他所有选手的总分。
选手 $3$ 也可以解决第 $4$ 题,总分将达到 $3703$ 分,超过其他所有选手的总分。

数据范围

• $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$。
• 输入中的所有数值都是整数。

来源

• AtCoder ABC323C