Кожна з \(N\) ферм фермера Джона (\(2\le N\le 10^5\)) вибрала команду з \(C\) корів (\(1\le C\le 18\)) для участі у дні поля. Порода кожної корови або Guernsey або Holstein.

Різниця між двома командами визначається як кількість позицій \(i\) (\(1 \leq i \leq C\)), при якому породи корів на \(i\)-х позиціях відрізняються. Для кожної команди \(t\) з \(1 \ldots N\) обчисліть максимальну різницю між командою \(t\) та будь-якою іншою командою.

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

Перший рядок містить \(C\) та \(N\).

Кожний з наступних \(N\) рядків містить рядок довжини \(C\) з G і H. Кожен рядок відповідає команді.

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

Для кожної команди виведіть максимальну різницю.

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

5 3
GHGGH
GHHHH
HGHHG

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

5
3
5

Перша та третя команди відрізняються на \(5\). Друга та третя команди відрізняються \(3\).

ОЦІНКА:

• Тести 2–5: \(C = 10\)
• Тести 6–9: Всі відповіді не нижче \(C-3\).
• Тести 10–20: додаткових обмежень немає.