B. Om Nom and Spiders
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Ом Ном очень любит конфеты и очень не любит пауков, поскольку последние частенько воруют конфеты. Как-то раз Ом Ном собрался на прогулку по парку. К сожалению, в парке водятся пауки, видеть которых Ом Ном совсем не хочет.

Парк можно представить как клетчатое поле n × m. В парке есть k пауков, каждый паук в момент времени 0 находится в некоторой клетке поля. Пауки все время двигаются, причем каждый паук всегда двигается в каком-то одном из четырех направлений (влево, вправо, вниз, вверх). За единицу времени паук из своей клетки переползает в соседнюю по стороне клетку в соответствующем направлении. Если в этом направлении клетки нет, то он покидает территорию парка. Пауки не мешают друг другу во время передвижения, в частности, в одно и то же время в одной клетке могут находиться несколько пауков.

Ом Ном еще не определился, откуда он начнет свою прогулку, но он точно хочет:

  • начать прогулку в момент времени 0 в одной из клеток верхней строки клетчатого поля (клетки этой строки гарантированно не содержат пауков);
  • во время всей прогулки двигаться вниз по полю по направлению к нижней строке (прогулка закончится, когда Ом Ном выйдет за пределы парка).

Ом Ном, как известно, передвигается прыжками. Один прыжок длится одну единицу времени и перемещает монстрика со своей клетки в соседнюю по стороне клетку поля следующей вниз строки, либо за пределы парка.

Каждый раз когда Ом Ном приземляется в какой-то клетке, он видит всех пауков, которые пришли в эту клетку в этот момент времени. Ом Ном хочет выбрать оптимальную клетку для начала прогулки. Поэтому ему интересно для каждой возможной стартовой клетки узнать, сколько пауков он увидит в процессе прогулки, если начнет из этой клетки. Помогите ему, посчитайте это количество для каждой возможной стартовой клетки.

Входные данные

В первой строке записано три целых числа 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-е число должно обозначать количество пауков, которое увидит Ом Ном, если начнет свою прогулку из j-й клетки первой строки. Клетки в строке клетчатого поля нумеруются слева направо.

Примеры
Входные данные
3 3 4
...
R.L
R.U
Выходные данные
0 2 2
Входные данные
2 2 2
..
RL
Выходные данные
1 1
Входные данные
2 2 2
..
LR
Выходные данные
0 0
Входные данные
3 4 8
....
RRLL
UUUU
Выходные данные
1 3 3 1
Входные данные
2 2 2
..
UU
Выходные данные
0 0
Примечание

Рассмотрим первый тестовый пример. Ниже показано, как будет меняться расположение пауков на поле в течение времени:


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

Символом «*» обозначена клетка, в которой находятся два паука одновременно.

  • Если Ом Ном начнет свой путь в первой клетке первой строки, тогда не вовсе не увидит пауков.
  • Если он начнет свой путь во второй клетке, тогда он увидит двух пауков в момент времени 1.
  • Если он начнет свой путь в третьей клетке, тогда он увидит двух пауков: одного в момент времени 1, а второго в момент времени 2.