CF436B.Om Nom and Spiders

Om Nom really likes candies and doesn't like spiders as they frequently steal candies. One day Om Nom fancied a walk in a park. Unfortunately, the park has some spiders and Om Nom doesn't want to see them at all.

The park can be represented as a rectangular n × m field. The park has k spiders, each spider at time 0 is at some cell of the field. The spiders move all the time, and each spider always moves in one of the four directions (left, right, down, up). In a unit of time, a spider crawls from his cell to the side-adjacent cell in the corresponding direction. If there is no cell in the given direction, then the spider leaves the park. The spiders do not interfere with each other as they move. Specifically, one cell can have multiple spiders at the same time.

Om Nom isn't yet sure where to start his walk from but he definitely wants:

• to start walking at time 0 at an upper row cell of the field (it is guaranteed that the cells in this row do not contain any spiders);
• to walk by moving down the field towards the lowest row (the walk ends when Om Nom leaves the boundaries of the park).

We know that Om Nom moves by jumping. One jump takes one time unit and transports the little monster from his cell to either a side-adjacent cell on the lower row or outside the park boundaries.

Each time Om Nom lands in a cell he sees all the spiders that have come to that cell at this moment of time. Om Nom wants to choose the optimal cell to start the walk from. That's why he wonders: for each possible starting cell, how many spiders will he see during the walk if he starts from this cell? Help him and calculate the required value for each possible starting cell.

奥姆·诺姆非常喜欢糖果，而非常讨厌蜘蛛，因为蜘蛛经常偷走他的糖果。一天，奥姆·诺姆想去公园散步。不幸的是，公园里有一些蜘蛛，而奥姆·诺姆完全不想见到它们。

公园可表示为一个 $n \times m$ 的矩形场地。公园中有 $k$ 只蜘蛛，每只蜘蛛在时刻 $0$ 位于场地中的某个格子上。蜘蛛始终在移动，且每只蜘蛛始终沿四个方向之一（左、右、下、上）移动。在单位时间内，一只蜘蛛从其当前格子爬行至对应方向上的相邻格子（即共享一条边的格子）。若该方向上不存在格子，则蜘蛛离开公园。蜘蛛在移动过程中互不干扰；特别地，同一时刻同一格子上可以有多个蜘蛛。

奥姆·诺姆尚未确定从哪个位置开始散步，但他明确希望：

• 在时刻 $0$ 从场地最上面一行的某个格子出发（题目保证该行所有格子初始时刻均无蜘蛛）；
• 向下穿越场地，朝最下面一行行走（当奥姆·诺姆离开公园边界时，此次行走结束）。

我们知道，奥姆·诺姆是通过跳跃来移动的。每次跳跃耗时一个单位时间，并将这个小怪物从当前格子传送到下方一行中相邻（即共享一条边）的格子，或直接传送至公园边界之外。

每次奥姆·诺姆降落在某个格子时，他都会看到在该时刻恰好到达该格子的所有蜘蛛。奥姆·诺姆希望选择最优的起始格子。因此他想知道：对每一个可能的起始格子，若从该格子出发行走，他在整个过程中将看到多少只蜘蛛？请帮助他计算每个可能起始格子所对应的该数值。

The first line contains three integers n, m, k (2 ≤ n, m ≤ 2000; 0 ≤ k ≤ m(n - 1)).

Each of the next n lines contains m characters — the description of the park. The characters in the i-th line describe the i-th row of the park field. If the character in the line equals ".", that means that the corresponding cell of the field is empty; otherwise, the character in the line will equal one of the four characters: "L" (meaning that this cell has a spider at time 0, moving left), "R" (a spider moving right), "U" (a spider moving up), "D" (a spider moving down).

It is guaranteed that the first row doesn't contain any spiders. It is guaranteed that the description of the field contains no extra characters. It is guaranteed that at time 0 the field contains exactly k spiders.

第一行包含三个整数 $n$、$m$、$k$（满足 $2 \leq n, m \leq 2000$；$0 \leq k \leq m(n-1)$）。

接下来的 $n$ 行，每行包含 $m$ 个字符，描述公园的布局。第 $i$ 行中的字符表示公园场地的第 $i$ 行。若某字符为 .，则表示对应格子为空；否则该字符必为以下四个字符之一：L（表示该格子在时刻 $0$ 有一只向左移动的蜘蛛）、R（向右移动的蜘蛛）、U（向上移动的蜘蛛）、D（向下移动的蜘蛛）。

保证第一行不包含任何蜘蛛。保证场地描述中不含额外字符。保证在时刻 $0$，场地上恰好有 $k$ 只蜘蛛。

Print m integers: the j-th integer must show the number of spiders Om Nom will see if he starts his walk from the j-th cell of the first row. The cells in any row of the field are numbered from left to right.

输出 m 个整数：其中第 j 个整数表示如果 Om Nom 从第一行的第 j 个单元格开始行走，他将看到的蜘蛛数量。场地中任意一行的单元格均从左至右编号。

Consider the first sample. The notes below show how the spider arrangement changes on the field over time:

... ... ..U ...
R.L -> .*U -> L.R -> ...
R.U .R. ..R ...

Character "*" represents a cell that contains two spiders at the same time.

• If Om Nom starts from the first cell of the first row, he won't see any spiders.
• If he starts from the second cell, he will see two spiders at time 1.
• If he starts from the third cell, he will see two spiders: one at time 1, the other one at time 2.

考虑第一个样例。下方的图示展示了蜘蛛在场地上的分布随时间变化的过程：

... ... ..U ...
R.L → .*U → L.R → ...
R.U .R. ..R ...

字符 “*” 表示一个在同一时刻包含两只蜘蛛的格子。

• 如果奥姆·诺姆从第一行的第一个格子出发，他将看不到任何蜘蛛。
• 如果他从第二个格子出发，他将在时刻 1 看到两只蜘蛛。
• 如果他从第三个格子出发，他将看到两只蜘蛛：一只出现在时刻 1，另一只出现在时刻 2。