ZOAC 7

시간 제한2초메모리 제한1024 MB

요약

N×M 격자의 각 칸에는 Z, O, A, C 중 하나가 적혀 있습니다. 왼쪽 위에서 오른쪽 아래로 오른쪽 또는 아래로만 이동하며 순간이동을 한 번 쓸 때, 각 문자를 최대 몇 개 모을 수 있는지 구합니다.

문제

Z, O, A, C로만 이루어진 $N$ 행 $M$ 열의 2차원 격자가 있다.

혁준이와 친구들은 $1$ 행 $1$ 열에서 출발하여 $N$ 행 $M$ 열까지 이동하며 문자들을 수집하려고 한다.

한 번의 이동에 오른쪽(열 번호가 증가하는 방향) 또는 아래(행 번호가 증가하는 방향)로만 한 칸씩 이동할 수 있다.

또한, 현재 칸이 $a$ 행 $b$ 열일 때 딱 한 번 $c > a$ 혹은 $d > b$ 를 만족하는 $c$ 행 $d$ 열로 순간이동을 할 수 있다.

다시 말해, 아래 그림의 초록색 칸에서 순간이동하는 경우, 보라색 칸들 중 한 곳으로 이동할 수 있다.

혁준: 나는 Z만 가져올거야!

익준: 그럼 나는 O만 가져올래.

동우: 나는 A만!

진우: 난 C만.

혁준이와 친구들이 각각 가져올 문자들의 최대 개수를 구해보자.

첫 번째 줄에 $N, M$ 이 주어진다. $(1 \le N,M \le 2\,000)$

$i+1$ 번째 줄에는 격자의 $i$ 행의 원소 $M$ 개가 공백을 사이에 두고 주어진다. $(1 \le i \le N)$

각 원소는 반드시 Z, O, A, C 중 하나이다.

각 문자 Z, O, A, C의 최대 수집 개수를 공백을 사이에 두고 출력한다.

Python 3 사용자는 PyPy3로 제출할 것을 권장한다.

예제 1

입력

3 5
Z Z O O A
A C C Z O
A C Z O A

예상 출력

4 4 4 3

예제 2

입력

5 6
A Z A C Z C
O C O Z A Z
O Z Z A O A
C Z A Z A C
Z O C O O Z

예상 출력

7 6 6 5