ZOAC 7

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로 제출할 것을 권장한다.