Om Nom và bầy nhện

Công viên là một bảng hình chữ nhật gồm $n$ hàng và $m$ cột. Trong công viên có $k$ con nhện, tại thời điểm $0$ mỗi con nhện đứng ở một ô nào đó. Mỗi con nhện luôn di chuyển theo một trong bốn hướng cố định: trái (L), phải (R), lên (U) hoặc xuống (D). Sau mỗi đơn vị thời gian, con nhện bò sang ô kề cạnh theo hướng của nó; nếu không còn ô theo hướng đó thì con nhện rời khỏi công viên và biến mất. Các con nhện không cản trở nhau, một ô có thể chứa nhiều nhện cùng lúc.

Om Nom bắt đầu đi dạo tại thời điểm $0$ từ một ô nào đó ở hàng trên cùng (đảm bảo hàng này không có nhện). Mỗi bước nhảy tốn đúng một đơn vị thời gian và đưa Om Nom từ ô hiện tại xuống ô ngay bên dưới cùng cột; khi đang ở hàng dưới cùng, bước nhảy tiếp theo sẽ đưa Om Nom ra khỏi công viên. Như vậy nếu xuất phát từ cột $j$, thì tại thời điểm $t$ Om Nom đứng ở ô nằm ở hàng $t$, cột $j$ (đánh số hàng từ $0$).

Mỗi lần Om Nom đáp xuống một ô, cậu nhìn thấy tất cả những con nhện đang có mặt tại ô đó ngay tại thời điểm ấy.

Với mỗi ô xuất phát ở hàng trên cùng, hãy tính tổng số con nhện Om Nom sẽ nhìn thấy trong suốt hành trình đi xuống của mình (một con nhện được đếm mỗi lần Om Nom gặp nó).

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự mô tả một hàng của công viên. Ký tự . là ô trống; các ký tự L, R, U, D là ô có một con nhện đang di chuyển theo hướng tương ứng.

Đảm bảo hàng đầu tiên không chứa con nhện nào và tổng số nhện đúng bằng $k$.

Dữ liệu ra

In ra $m$ số nguyên trên một dòng: số thứ $j$ là số con nhện Om Nom nhìn thấy nếu xuất phát từ ô thứ $j$ của hàng trên cùng (các cột được đánh số từ trái sang phải).

Ràng buộc

• $2\le n,m\le 2000$
• $0\le k\le m(n-1)$

Ví dụ