Masala #0851

Xotira 32 MB Vaqt 1000 ms

Labirintdagi Xazina

Bolek va Lolek ni hamma yaxshi tanisa kerak. Tinib tinchimas sayohatchilarning qo'liga yashirin xazinaning xaritasi tushib qoldi. Xaritada labirint tasvirlangan bo'lib, Labirint \(n×m\) o'lchamda va atrofi devor bilan o'ralgan, unga kirish eshiklari tepadagi ikki burchakda. Dastlab aka-uka chizmani yaxshilab o'rganishdi va labirint tomon yo'lga tushishdi. Bolek o'zini aqlli deb bilgani uchun xazinani bo'lishib olishga ko'nmay janjallashdi va ikkalasi xazinani ikki tomondan izlashga qaror qildi. Lolek birinchi eshikdan kirib labirintning yuqori chap burchagidan, Bolek esa ikkinchi eshikdan kirib labirintning yuqori o'ng burchagidan yurishni boshlaydi. Ularning tezliklari bir xil bo'lib, siz xazinaga kim birinchi bo'lib borishini va aka-uka xazinagacha qancha yo'l bosishini aniqlashingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\), \(m\)\((4 \le n,m \le 2*10^3)\) mos ravishda labirint bo'yi va eni kiritiladi. Keyingi \(n\) ta qatorda \(m\) tadan belgi kiritiladi. «#» - devor, «.» - bo'sh joy, «X» xazina turgan joyni anglatadi. Tushunish uchun Izoh ga qarang.

Chiquvchi ma'lumotlar:

Birinchi qatorda Lolek va Bolek ning xazinaga yetib borgunicha minimum qancha masofa bosishi kerakligini probel bilan ajratib chiqaring. Ikkinchi qatorda g'olibning ismini, agar ikkisi bir vaqtda yetib borsa Draw! deb chiqaring.

Misollar

#	input.txt	output.txt
1	8 12 ############ #...#......# #.......##.# #..#......## ###.##.###.# #....#...#.# #..##.#X#..# ############	11 10 Bolek

Izoh:

Birinchi testda yurishlar taxminan mana shunday bo'ladi:

############
#L++#..+++B#
#..+++.+##.#
#..#.+++..##
###.##+###.#
#....#++.#.#
#..##.#X#..#
############

to'q sariq rangda Labirint eshiklari
qizil rangda Lolekning taxminiy marshruti
yashil rangda Bolekning taxminiy marshruti
L va B Lolek va Bolekning dastlabki nuqtalari belgilangan.