ZOAC 7

Time limit2sMemory limit1024 MB

Summary

Given an N by M grid of Z, O, A, and C, find the maximum count of each letter on a right-or-down path from the top-left to the bottom-right cell that may teleport once.

Level: Medium7 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

A grid of $N$ rows and $M$ columns is given, and each cell contains one of Z, O, A, C.

Hyukjun and his friends start at row 1, column 1 and move to row $N$ , column $M$ , collecting characters along the way.

Each move goes one cell to the right (increasing column number) or one cell down (increasing row number).

Also, when the current cell is row $a$ , column $b$ , you may teleport exactly once to row $c$ , column $d$ that satisfies $c > a$ or $d > b$ .

Put differently, when teleporting from a green cell in the figure below, you can land on any of the purple cells.

Hyukjun: I will only take Z!

Ikjun: Then I will only take O.

Dongwoo: I will only take A!

Jinwoo: I only take C.

Find the maximum number of characters that Hyukjun and his friends can each collect.

Input

The first line contains $N$ and $M$ . $(1 \le N,M \le 2\,000)$

The next $N$ lines each contain $M$ elements of row $i$ of the grid, separated by spaces. $(1 \le i \le N)$

Each element is one of Z, O, A, C.

Output

Print the maximum number of collected characters for each of Z, O, A, C, separated by spaces.

Hint

Python 3 users are recommended to submit with PyPy3.

Examples2

Example 1

Input

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

Expected output

4 4 4 3

Example 2

Input

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

Expected output

7 6 6 5