Qnom qəsrdə

Düzbucaqlı N \times M ölçülü matrisdə qədim bir qalanın planı şifrələnib. Planın hər bir hüceyrəsi bir tam ədəd $A$ (0 \leq A \leq 31) ilə göstərilib, bu ədəd aşağıdakı qaydalara əsasən rəqəmlərin cəminə bərabərdir:

• qərbdə divar varsa, $1$;

• şimalda divar varsa, $2$;

• şərqdə divar varsa, $4$;

• cənubda divar varsa, $8$;

• hüceyrədə bir kisə qızıl varsa, $16$;

Daxili divar iki hüceyrə tərəfindən paylaşılır. Məsələn, $(1,2)$ hüceyrəsinin cənub divarı həm də $(2,2)$ hüceyrəsinin şimal divarıdır (bax: illüstrasiya və nümunə giriş faylı).

Əgər sərhəd üzərində yerləşən bir hüceyrənin uyğun xarici divarı yoxdursa, o zaman bu hüceyrə çıxış hüceyrəsi adlanır. İllüstrasiyada iki belə hüceyrə göstərilib: $(2,1)$ və $(1,5)$. Ümumi olaraq, çıxış hüceyrələrinin sayı $10$-dan çox deyil.

Cırtdan verilmiş $(i,j)$ koordinatında yerləşir. O, qəsrin divarları maneə olmadan yan-yana olan hüceyrələr arasında keçərək hərəkət edə bilər. Cırtdan yalnız bir ədəd qızıl kisəsini daşıya bilər (birdən artıq yox). Cırtdanın məhz bir kisə qızıl toplayaraq istənilən çıxış hüceyrəsinə minimum neçə addım $K$-da çata biləcəyini tapın.