Description

小明正在参加一场编程比赛 World Tour Finals，该比赛已经进行到一半，场上共有 $N$ 名选手参加，还有 $M$ 道题目尚未全部解答。

每道题的分值 $A_i$ 是 100 的倍数，且范围在 500 到 2500 之间。对于每个选手 $i$，给定一个字符串 $S_i$，表示该选手目前的解题情况。字符串的长度为 $M$，其中第 $j$ 个字符为 'o' 表示选手 $i$ 已经解决了第 $j$ 道题目，为 'x' 表示该选手尚未解决该题。

每个选手的总分由两个部分组成：

1. 已经解决题目的分数总和。
2. 选手编号作为额外分数（第 $i$ 号选手获得 $i$ 分额外分数）。

对于每个选手 $i$，需要计算的是：

为了超过其他所有选手的当前总分，选手 $i$ 还需要再解决至少几道题目？请注意，每个选手 $i$ 都可以通过解完剩下的题目，超过所有其他选手的当前总分，因此答案总是定义明确的。

Format

Input

N M
A_1 A_2 ... A_M
S_1
S_2
...
S_N

第一行包含两个整数 $N$ 和 $M$，分别表示选手数量和题目数量。

第二行包含 $M$ 个整数，表示每道题目的分数 $A_i$。

接下来的 $N$ 行中，第 $i$ 行是一个长度为 $M$ 的字符串 $S_i$，表示选手 $i$ 的解题情况。

Output

输出 $N$ 行。第 $i$ 行应包含一个整数，表示选手 $i$ 需要再解决的最少题目数量，才能超过其他所有选手的当前总分。

Samples

样例输入 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

样例输出 1

0
1
1

样例解释

• 选手 1 的当前总分为 $2001$ 分。
• 选手 2 的当前总分为 $1502$ 分。
• 选手 3 的当前总分为 $1703$ 分。

选手 1 已经领先其他所有选手，无需再解决任何题目。 选手 2 和 选手 3 可以分别解决第 4 题，从而超过其他所有选手的当前总分。

样例输入 2

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

样例输出 2

1
1
1
1
0

样例解释

• 选手 5 已经领先其他所有选手，无需再解决任何题目。
• 其他选手各自只需解决一道题目即可超越其他选手。

样例输入 3

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

样例输出 3

7
6
5
4
3
2
0

Limitation

1s 256MB

约束条件

• $2 \leq N \leq 100$
• $1 \leq M \leq 100$
• $500 \leq A_i \leq 2500$
• $A_i$ 是 100 的倍数
• $S_i$ 是一个由 'o' 和 'x' 组成的长度为 $M$ 的字符串
• 每个选手至少有一道题尚未解答（即 $S_i$ 中至少有一个 'x'）。