Триває змагання з програмування World Tour Finals, де бере участь \(N\) гравців, а половина змагального часу пройшла. У цьому конкурсі є \(M\) задач, і оцінка \(A_i\) ​ задачі \(i\) є кратною 100 від 500 до 2500 включно.

Для кожного \(i=1,…,N\) вам надається рядок \(S_i\) ​, який вказує, які задачі гравець \(i\) вже розв’язав. \(S_i\) ​ — це рядок довжини \(M\), що складається з 'o' та 'x', де \(j\)-й символ \(S_i\) ​ дорівнює 'o', якщо гравець \(i\) вже розв’язав задачу \(j\), і 'x', якщо він ще не розв’язав її. Тут ще ніхто з гравців не розвʼязав усіх задач.

Загальна кількість балів гравця \(i\) розраховується як сума балів розв’язаних задач плюс бонусна кількість балів \(i\). Для кожного \(i=1,…,N\) дайте відповідь на таке запитання.

• Принаймні скільки завдань, які гравець \(i\) ще не розв’язав, повинен розвʼязати гравець \(i\), щоб перевищити поточну загальну кількість балів усіх інших гравців?

Зауважте, що за умов цього твердження та обмежень можна довести, що гравець \(i\) може перевищити поточні загальні бали всіх інших гравців, розв’язавши всі задачі, тому відповідь завжди є.

Обмеження

• \(2≤N≤100\)
• \(1≤M≤100\)
• \(500≤A_i ​ ≤2500\)
• \(A_i\) ​ кратне 100.
• \(S_i\) ​ це рядок довжини \(M\), що складається з 'o' та 'x'.
• \(S_i\) ​ містить принаймні один 'x'.
• Усі числові значення у вхідних даних є цілими.

Формат вхідних даних

Перший рядок містить цілі числа \(N,M\).

Наступний   рядок містить \(M\) цілих чисел \(A_i\).

Наступні  \(N\) рядків містять \(S_i\).

Формат вихідних даних

Вивести \(N\) рядків.

В \(i\)-му рядку має бути відповідь на запитання щодо гравця \(i\).

Приклад вхідних даних

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Приклад вихідних даних

0
1
1

Загальні результати гравців на середині часу змагання становлять 2001 бал для гравця 1, 1502 бали для гравця 2 і 1703 бали для гравця 3.

Гравець 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