题目背景

翻译自「AtCoder ABC323C」

题目描述

有 $N$ 名选手参加的编程比赛世界巡回赛决赛正在进行中，比赛时间已经过半。

这场比赛共有 $M$ 道题目，第 $i$ 题的分值 $A_i$ 是 $500$ 到 $2500$ 之间的 $100$ 的倍数。

对于每个 $i=1,\cdots,N$, 给出一个字符串 $S_i$ 表示选手 $i$ 已经解决了哪些题目。

$S_i$​ 是一个长度为 $M$ 的由 o 和 x 组成的字符串，其中 $S_i$ 的第 $j$ 个字符为 o 表示选手 i 已经解决了第 j 题，为 x 表示还没有解决。

这里,没有选手解决了所有题目。

选手 $i$ 的总分计算为其解决的题目分值之和，再加上 $i$ 分的奖励分。

现在,对于每个 $i=1,\cdots,N$，请回答以下问题:

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

注意，根据题目中的条件和约束，可以证明选手 $i$ 通过解决所有题目，可以超过其他所有选手目前的总分，因此答案始终是有定义的。

输入格式

第一行输入两个整数 $N$ 和 $M$。

第二行输入 $M$ 个整数 $A_1,A_2,\cdots,A_M$。

接下来有 $N$ 行，每行输入一个字符串 $S_i$。

输出格式

输出 $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\le N\le 100,1\le M\le 100,500 \le A_i \le 2500$，且 $A_i$ 是 $100$ 的倍数。

$S_i$ 是一个长度为 $M$ 的由 o 和 x 组成的字符串，$S_i$ 至少包含一个 x。