PROGRAMING PROBLEMS

N мөр, М баганатай тэгш өнцөгт хүснэгтэд К робот байна. Хуснэгтийн мөрийг 1-ээс N хуртэлх тоогоор, баганыг 1-ээс М хүртэлх тоогоор дугаарлана. 

Эхлээд робот тэгш өнцөгтийн аль нэг нүднээс ажлаа эхлах ба секунд тутамд дараах үйлдлүүдийг хийдэг. Үүнд: 

1. Тухайн нүдэн дэх X тоог уншина. 

2. Х удаа цагийн зүүний дагуу 90 градус эргэнэ. 

3. Хүснэгтийн хил дээрх нүдэнд байрласан ба гадагшаа харж байгаа бол 180 градус эргэнэ. 

4. Эцэст нь тухайн хөрш нүд рүүгээ шилжинэ.

Хүснэгтийн нэг нүдэнд урхи тавьсан байгаа. Урхи нь роботыг нег секундийн дотор цэнэггүй болгодог. Тэгвэл робот цэнэггүй болтлоо хичнээн секунд болохыг тодорхойлно уу.

Оролт

Оролтын эхний мөрөнд N (3 <= N <= 50), M (3 <= M <= 50), K (1 <= K <= 5) эерэг бүхал тоонууд байна. 

Оролтын хоёр дахь мөрөнд зэрэг бүхэл X ба Y тоонууд нь урхи тавьсан мөр ба баганын дугаар байна. 

Оролтын үлдсан мөрүүд нь 1-ээс К хүртэлх робот бүрийн хувьд тодорхойлолтыг харуулна. 

Үүнийг тайлбарлавал: 

 - Xi , Yi хоёр зэрэг бүхэл тоо нь і дүгээр роботын эхлэлийн нүдний мөр ба багана ба роботын эхлэлийн чиглэлийг илэрхийлэх Сі тэмдэгт (U - дээш, R - баруун, D -доош, L - зуун) байна. 

 - N мөр бүр нь 0-ээс 9 хүртэлх М цифрүүдээс тогтох ба үүнд х мөр ба у баганын цифр нь і дүгээр роботын үйлдэлд зориулсан (х, у) нуд дэх утгыг илэрхийлнэ.

Гаралт

Гаралтын ганц мөрөнд робот урхинд орж зогсох хүртлээ зарцуулах нийт хугацааг секундээр гаргана. Хэрэв робот хэзээ ч зогсохгуй бол -1 гарна.

Жишээ

Оролт1

3 3 1

2 2

1 1 R

010

000

000

Гаралт1

3

Оролт2

3 4 2

2 2

3 4 R

2327

6009

2112

3 2 R

1310

2101

1301

Гаралт2

8

Оролт3

4 4 3

4 3

1 1 U

1001

0240

3322

2327

1 3 L

9521

2390

3020

2421

2 2 D

3397

2013

1102

7302

Гаралт3

296