436B орчуулах · Codeforces.mn

# Ум Ном ба аалзнууд
Ум Ном чихрэнд үнэхээр дуртай, тэр байнга чихэр хулгайлдаг аалз шиг биш юм. Нэг өдөр Ум Ном паркаар алхаж байв. Харамсалтай нь паркад аалз байгаа бөгөөд Ум Ном тэднийг харахыг хүсэхгүй байв.
![](http://espresso.codeforces.com/5be91a371adfaffc95d78b5f3caf8c1149be2c29.png)

Паркыг $n × m$ тэгш өнцөгт талбайгаар илэрхийлж болно. Паркад к аалз байгаа ба, аалз бүр 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$-р тоо нь түүний харсан аалзны тоо юм. Талбайн ямар ч эгнээний хэсэг нь зүүнээс баруун тийш дугаарлагдсан.

## Тэмдэглэл

Эхний жишээг авч үзье. Доорх тэмдэглэл нь аалз хугацааны туршид талбай дээр хэрхэн өөрчлөлт хийснийг харуулж байна:
    
    
      
    ...        ...        ..U       ...  
    R.L   ->   .*U   ->   L.R   ->  ...  
    R.U        .R.        ..R       ...

"$*$" тэмдэг нь ижил хугацаанд хоёр аалз агуулсан хэсгийг илэрхийлнэ.

* Хэрвээ Ум Ном эхний эгнээний эхний хэсгээс эхэлсэн бол ямар ч аалз харахгүй.
  * Хэрвээ тэр хоёр дахь хэсгээс эхэлсэн бол 1 нэгж хугацаанд хоёр аалз харна.
  * Хэрвээ тэр гурав дахь хэсгээс эхэлсэн бол хоёр аалз харна: 1 нэгж хугацаанд 1-ийг, нөгөө нэгийг нь 2 нэгж хугацаанд харна.

-- Даариймаа

Жишээ тэстүүд

Оролт

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