Cho một bảng các chữ cái. Nhiệm vụ của bạn là tính, với mỗi chữ cái, số lưới con hình vuông mà mọi ô trong đó đều chứa chữ cái đó.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\): kích thước của bảng và số lượng chữ cái. Các chữ cái là \(k\) chữ cái in hoa đầu tiên.

Sau đó có \(n\) dòng mô tả bảng. Mỗi dòng chứa \(n\) chữ cái.

Output

In ra \(k\) dòng: với mỗi chữ cái, số lưới con tương ứng.

Constraints

• \(1 \le n \le 3000\)

• \(1 \le k \le 26\)

Example

5 3
ABBBC
BBBBC
BCAAA
AAAAA
AAAAA

21
10
3