题目描述

本题与“私人教练（Trener osobisty）”完全相同，仅数据范围更大。

Bajtazar 的身体状态用 $(m,r)$ 表示。每天可按给定规则把 $m$ 或 $r$ 增加 $1$。每个状态的规则字符为：

• M：只能到 $(m+1,r)$；
• R：只能到 $(m,r+1)$；
• O：两者任选。

Bajtazar 可以随时停止训练，也可以不开始训练。对于每个初始状态 $(m,r)$，求能够到达并作为结束状态的不同状态数量。

输入格式

第一行两个整数 $M,R$，满足 $1\le M,R\le3000$。

接下来 $R$ 行，每行恰好 $M$ 个字符。最后一行最后一个字符是 X，对应 $(M,R)$；其他位置为 M、R 或 O。

题目保证所有指定转移均不会越界。

输出格式

输出 $R$ 行，每行 $M$ 个整数。第 $r$ 行第 $m$ 个整数表示从 $(m,r)$ 出发可到达的结束状态数量。

样例输入

5 4
OMROR
OMROR
OMROR
MMMMX

样例输出

14 7 6 8 4
11 6 5 6 3
8 5 4 4 2
5 4 3 2 1