#P17302. [ONTAK 2014] 私人教练(Trener osobisty)

[ONTAK 2014] 私人教练(Trener osobisty)

题目描述

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

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

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

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

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

输入格式

第一行两个整数 M,RM,R,满足 1≤M,R≤10001\le M,R\le1000。

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

对于其他状态 (m,r)(m,r),对应字符为 M、R 或 O,含义如题目描述。题目保证所有指定转移都不会越出允许范围。

输出格式

输出 RR 行,每行 MM 个整数。

第 rr 行第 mm 个数表示从初始状态 (m,r)(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