• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

آدرینا یک آدم گریز است. امروز در مسیر حرکت خود از خانه به حلقه‌ی آدم گریزان، مجبور است از پارکی پر از آدم بگذرد. پارک به شکل یک مستطیل \(m \times n\) است و تعدادی آدم در آن در حال قدم زدن هستند. او می‌خواهد از ضلع بالایی آن به ضلع پایینی پارک برسد و طبق تجربیات گذشته خود نیز می‌داند که اگر در یک مسیر مستقیم حرکت کند، امیدِ ریاضی تعداد آدم هایی که می‌بیند کم‌تر است!

در لحظه‌ای که آدرینا به پارک می‌رسد تعداد \(k\) نفر آن‌جا هستند که هرکدام به یکی از جهت‌های بالا (U)، پایین (D)، چپ (L) یا راست (R) هستند و هر ثانیه یک خانه در جهت خود حرکت می‌کنند. آدرینا نیز هر ثانیه یک خانه به سمت پایین حرکت می‌کند و تنها در صورتی یک آدم را می‌بیند که در یک زمان با او در یک خانه قرار گیرد.

آدرینا می‌خواهد بداند به ازای گذر از هر مسیر موجود، چندتا آدم می‌بیند که در نهایت کم آدم ترین مسیر را انتخاب کند. دقت کنید آدم‌ها هر لحظه به مسیر خود ادامه می‌دهند و در انتهای مسیر از پارک خارج می‌شوند.

تضمین می‌شود در لحظه شروع در هیچ خانه‌ای دو آدم قرار ندارد و هم چنین هیچ آدمی در ضلع بالایی (محل شروع حرکت آدرینا) نیست.

ورودی

در خط اول ورودی سه عدد \(n\) و \(m\) و \(k\) آمده‌اند که به ترتیب طول و عرض پارک و تعداد آدم‌ها در لحظه ورود به پارک را نشان می‌دهد. در \(n\) خط بعدی هر خط یک رشته متشکل از \(m\) حرف می‌آید که پارک را نشان می‌دهند. در هر خانه یا کسی نیست که با نقطه نشان شده است و یا یک نفر در آن خانه قرار دارد که با یکی. از حروف R، L، D، U جهت حرکت آن را مشخص کرده‌ایم.

\[2 \leq n, m \leq 1000\] \[0 \leq k \leq (n - 1) \times m\]

خروجی

در تنها خط خروجی \(m\) عدد با فاصله از هم چاپ شود که \(i\)امین آن تعداد آدم‌هایی است که آدرینا با شروع حرکت از خانه \(i\)ام سطر اول آن‌ها را می‌بیند.

مثال‌ها

ورودی نمونه ۱

3 3 4
...
R.L
R.U

خروجی نمونه ۱

0 2 2

ورودی نمونه ۲

2 2 2
..
RL

خروجی نمونه ۲

1 1

ورودی نمونه ۳

2 2 2
..
LR

خروجی نمونه ۳

0 0