Ом Ном очень любит конфеты и очень не любит пауков, поскольку последние частенько воруют конфеты. Как-то раз Ом Ном собрался на прогулку по парку. К сожалению, в парке водятся пауки, видеть которых Ом Ном совсем не хочет.
Парк можно представить как клетчатое поле n × m. В парке есть k пауков, каждый паук в момент времени 0 находится в некоторой клетке поля. Пауки все время двигаются, причем каждый паук всегда двигается в каком-то одном из четырех направлений (влево, вправо, вниз, вверх). За единицу времени паук из своей клетки переползает в соседнюю по стороне клетку в соответствующем направлении. Если в этом направлении клетки нет, то он покидает территорию парка. Пауки не мешают друг другу во время передвижения, в частности, в одно и то же время в одной клетке могут находиться несколько пауков.
Ом Ном еще не определился, откуда он начнет свою прогулку, но он точно хочет:
- начать прогулку в момент времени 0 в одной из клеток верхней строки клетчатого поля (клетки этой строки гарантированно не содержат пауков);
- во время всей прогулки двигаться вниз по полю по направлению к нижней строке (прогулка закончится, когда Ом Ном выйдет за пределы парка).
Ом Ном, как известно, передвигается прыжками. Один прыжок длится одну единицу времени и перемещает монстрика со своей клетки в соседнюю по стороне клетку поля следующей вниз строки, либо за пределы парка.
Каждый раз когда Ом Ном приземляется в какой-то клетке, он видит всех пауков, которые пришли в эту клетку в этот момент времени. Ом Ном хочет выбрать оптимальную клетку для начала прогулки. Поэтому ему интересно для каждой возможной стартовой клетки узнать, сколько пауков он увидит в процессе прогулки, если начнет из этой клетки. Помогите ему, посчитайте это количество для каждой возможной стартовой клетки.
Выходные данные
Выведите m целых чисел: j-е число должно обозначать количество пауков, которое увидит Ом Ном, если начнет свою прогулку из j-й клетки первой строки. Клетки в строке клетчатого поля нумеруются слева направо.
Примечание
Рассмотрим первый тестовый пример. Ниже показано, как будет меняться расположение пауков на поле в течение времени:
... ... ..U ...
R.L -> .*U -> L.R -> ...
R.U .R. ..R ...
Символом «*» обозначена клетка, в которой находятся два паука одновременно.
- Если Ом Ном начнет свой путь в первой клетке первой строки, тогда не вовсе не увидит пауков.
- Если он начнет свой путь во второй клетке, тогда он увидит двух пауков в момент времени 1.
- Если он начнет свой путь в третьей клетке, тогда он увидит двух пауков: одного в момент времени 1, а второго в момент времени 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 4
...
R.L
R.U
|
0 2 2
|
|
2
|
2 2 2
..
RL
|
1 1
|
|
3
|
2 2 2
..
LR
|
0 0
|
|
4
|
3 4 8
....
RRLL
UUUU
|
1 3 3 1
|
|
5
|
2 2 2
..
UU
|
0 0
|