Условие

---

CODE@BURGAS 2026, ГРУПА C, ЗАДАЧА D. ЛАБИРИНТ С ПАМЕТ, ТЕЛЕПОРТИ И ЦЕНА
---
Вие сте в лабиринт с размери n x m и трябва да намерите най-евтиния път от началната клетка (0,0) до крайната клетка (n-1,m-1). Лабиринтът е представен като двумерен масив със следните стойности: 
- стойност -1 означава стена (непроходимо поле) 
- стойност 0 означава свободно поле с цена 1 
- положително число k означава поле с цена k 
- стойност -2 означава телепорт 
Позволени са движения в четири посоки: нагоре (U), надолу (D), наляво (L) и надясно (R). Ако стъпите върху телепорт, можете да се преместите до всеки друг телепорт в лабиринта без допълнителна цена (само цената за влизане в клетката се заплаща). Не можете да посещавате една и съща клетка повече от веднъж. Целта е да намерите път с минимална обща цена. 

Ограничения:
1 ≤ n, m ≤ 200. 

Вход:
На първия ред на стандартния вход се въвеждат две цели числа n и m — съответно броят на редовете и колоните на лабиринта. Следват n реда, всеки съдържащ по m цели числа, които описват клетките на лабиринта. Всяко число може да има една от следните стойности: -1 — клетката е стена и не може да бъде премината; 0 — свободна клетка с цена за преминаване 1; положително цяло число k — клетка с цена за преминаване k; -2 — клетка, представляваща телепорт. Началната позиция винаги е в клетката (0, 0), а крайната позиция — в клетката (n-1, m-1).

Изход:
Ако съществува път от началната до крайната клетка, изведете този път като последователност от символи: U — движение нагоре, D — движение надолу, L — движение наляво и R — движение надясно. Пътят трябва да е с минимална обща цена. Ако не съществува такъв път, изведете: NO SOLUTION 
 

Примерен вход:
10 4
0 0 -1 1 
0 -1 0 -2 
0 2 -2 -1 
-1 0 3 5 
0 -2 0 1 
-1 4 -1 1 
-2 -2 0 3 
0 -1 1 5 
0 1 0 4 
-1 0 -1 0

Примерен изход: 
DDRRRDDRD