题目描述

Bajtazar 的身体状态用一对正整数 $(m,r)$ 表示，分别代表“质量”和“线条”。每天训练后，他必须使其中一个值增加 $1$。

根据每天开始时的状态 $(m,r)$，教练给出了三种可能的要求：

• M：只能从 $(m,r)$ 转移到 $(m+1,r)$；
• R：只能从 $(m,r)$ 转移到 $(m,r+1)$；
• O：可以在上述两种转移中任选一种。

Bajtazar 可以在任意时刻停止训练，也可以一天都不训练，但状态始终不能超过 $m\le M$、$r\le R$。

对于每一个可能的初始状态 $(m_1,r_1)$，求他最终可以在多少个不同状态 $(m_2,r_2)$ 停止训练。

输入格式

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

接下来 $R$ 行，每行恰好 $M$ 个字符。最后一行最后一个字符为 X，对应状态 $(M,R)$。

对于其他状态 $(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