Bạn được cho một lưới 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 chữ nhật có viền chỉ gồm chữ cái đó.

Input

Dòng đầu tiên gồm hai số nguyên \(n\) và \(k\): kích thước của lưới 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ả lưới. Mỗi dòng gồm \(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 500\)

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

Example

5 3
ABBBC
ABABC
ABBBC
ABBBC
CCCCC

11
38
29