Om Nom 非常喜欢糖果,但不喜欢蜘蛛,因为它们经常偷糖果。有一天,Om Nom 想去公园散步。不幸的是,公园里有一些蜘蛛,Om Nom 根本不想看到它们。
公园可以表示为一个 n × m 的矩形场地。公园里有 k 只蜘蛛,每只蜘蛛在时间 0 时都在场地的某个单元格中。蜘蛛一直在移动,并且每只蜘蛛总是沿着四个方向之一移动(左、右、下、上)。在一个单位时间内,一只蜘蛛从自己的单元格中沿着相应的方向爬行到旁边相邻的单元格中。如果给定方向上没有单元格,那么蜘蛛就会离开公园。蜘蛛在移动时不会互相干扰。具体来说,一个细胞可以同时拥有多个蜘蛛。
Om Nom 还不确定从哪里开始步行,但他肯定想要:
- 在时间 0 处开始在田地的上排单元格行走(保证该行单元格不包含任何蜘蛛);
- 沿着场地向最低行移动(当 Om Nom 离开公园边界时步行结束)。
我们知道 Om Nom 通过跳跃来移动。一次跳跃需要一个时间单位,并将小怪物从他的牢房运送到下排的侧面相邻牢房或公园边界外。
每次 Om Nom 降落在牢房中时,他都会看到此时来到该牢房的所有蜘蛛。 Om Nom 想要选择最佳的单元格来开始步行。这就是为什么他想知道:对于每个可能的起始单元,如果他从这个单元出发,在步行过程中他会看到多少只蜘蛛?帮助他计算每个可能的起始单元格所需的值。
输入
第一行包含三个整数 n、m、k (2 ≤ n, m ≤ 2000; 0 ≤ k ≤ m(n - 1))。
接下来的 n 行每行包含 m 个字符——公园的描述。第 i 行中的字符描述了公园场地的第 i 行。如果该行中的字符等于“.”,则表示该字段对应的单元格为空;否则,该行中的字符将等于以下四个字符之一:“L”(表示该单元格在时间 0 处有一只蜘蛛,向左移动)、“R”(向右移动的蜘蛛)、“U”(向上移动的蜘蛛)、“D”(向下移动的蜘蛛)。
保证第一行不包含任何蜘蛛。保证字段的描述不包含多余的字符。保证在时间 0 时该字段恰好包含 k 个蜘蛛。
输出
打印 m 个整数:第 j 个整数必须显示 Om Nom 从第一行的第 j 个单元格开始行走时将看到的蜘蛛数量。该字段中任意行中的单元格均从左到右编号。
示例
输入 #1
3 3 4 ... R.L R.U
输出 #1
0 2 2
输入 #2
2 2 2 .. RL
输出 #2
1 1
输入 #3
2 2 2 .. LR
输出 #3
0 0
输入#4
3 4 8 .... RRLL UUUU
输出#4
1 3 3 1
输入 #5
2 2 2 .. UU
输出 #5
0 0
注意
考虑第一个样本。下面的注释显示了蜘蛛在场地上的排列如何随着时间的推移而变化:
字符“*”代表同时包含两只蜘蛛的单元格。
- 如果 Om Nom 从第一行的第一个单元格开始,他将不会看到任何蜘蛛。
- 如果他从第二个单元格开始,他会在时间 1 看到两只蜘蛛。
- 如果他从第三个单元格开始,他会看到两只蜘蛛:一只在时间 1,另一只在时间 2。