F. Уралдаан

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хуучин хот нь $m × n$ хэмжээтэй блокуудын хүснэгтээр дүрслэгдэх тэгш өнцөгт хот юм. Уг хот нь олон барилгууд, 2 урсгалтай шулуун гудамжнууд болон замын уулзварууд агуулдаг. Замын уулзвар болон барилга болгон нь яг нэг блок байх юм. Бүх гудамжнууд нь нэг блок өргөнтэй ба босоо эсвэл хэвтээ гудамжнууд байна. Мөн гудамж болгоны 2 талд нь нэг уулзвар байдаг. Хэрэв 2 блокын хувьд зөвхөн уг 2 блок ерөнхий талтай байвал уг 2 блокийг зэргэлдээ гэж нэрлэнэ. Ялгаатай гудамжнуудын ямар ч 2 блок нь нь зэргэлдээ биш бөгөөд ямар ч 2 замын уулзварууд нь зэргэлдээ биш байх юм.

Уг хотод жилд нэг удаа болдог арга хэмжээ нь одоо болж байгаа бөгөөд хөгшин Пэйкан үүний нэг хэсэг болон хот дотор байх тусгай замыг даган явж байв. Уг зам нь гудамжны нэгэн блокоос эхлэх ба маш олон замын уулзварыг өнгөрөн явсаар ямар нэгэн гудамжны нэгэн блок дээр дуусах юм. Бүх гудамжны блокийн хувьд бид хөгшин Пэйкан уг блокоос үүний зэргэлдээ блок уруу явахад хэчнээн хэмжээний хугацаа зарцуулахыг мэдэж байгаа. Мөн хөгшин Пэйкан нь замын уулзвар бүрээс үүний зэргэлдээ замын блок хүртэл нэг минут явдаг. Мэдээж хэрэг хөгшин Пэйкан барилга байгаа блок уруу явж чадахгүй.

Бид хөгшин Пэйкан-ын анхны байрлал болон өөрийн эцсийн зогсоолдоо хүрэхийн тулд түүний өнгөрч явах замын уулзваруудын дарааллыг мэдэж байгаа. Бүх замын уулзваруудыг өнгөрсний дараа эцсийн зогсоолдоо хүрэх ба тэндээ үүрд үлдэх юм. Таны даалгавар бол хөгшин Пэйкан хөдөлж эхэлснээс хойш $k$ минутын дараа хаана байхыг олох юм. Өгөгдсөн замын уулзваруудаар дамжин эцсийн зогсоолдоо хүрэхдээ хөгшин Пэйкан үргэлж хамгийн богино замаар явна гэж үзнэ үү.

Хөгшин Пэйкан зарим блокоор нэгээс олон удаа дайрч болохыг анхаарна уу.

Оролт

Эхний мөрөнд 3 бүхэл тоо тоо $m$, $n$ болон $k$ $(3 ≤ m, n ≤ 100, 1 ≤ k ≤ 100000)$ өгөгдөнө. Дараагийн $m$ мөрөнд хотын газрын зургийг дүрсэлнэ. Эдгээр мөрүүд нь тус бүр нь $n$ ширхэг тэмдэгт агуулах ба тэмдэгт болгон нь блок байна:

  • "$#$" тэмдэгт нь барилгыг дүрсэлнэ.
  • "$1$", "$2$", $...$, "$9$" цифрүүд нь гудамжны блокийг илэрхийлэх ба эдгээр цифрүүд нь хөгшин Пэйкан уг блокоор дамжин гарахад шаардагдах минутын тоог илэрхийлнэ.
  • "$a$", "$b$", $...$, "$z$" тэмдэгтүүд нь уг блок нь замын уулзвар болохыг илэрхийлэх ба эдгээр тэмдэгтүүд нь уг уулзварын нэр байх юм. Бүх уулзваруудын нэр нь цорын ганц байна.

Бүх блокууд нь координатуудтай гэж үзнэ: $i$-дах мөрийн $j$-дэх блок нь
$(i, j)$ $(1 ≤ i ≤ m, 1 ≤ j ≤ n)$ координаттай байна.

$(m + 2)$-дахь мөрөнд 2 бүхэл тоо $r_{s}$ болон $c_{s}$ $(1 ≤ r_{s} ≤ m, 1 ≤ c_{s} ≤ n)$, тэмдэгт мөр $s$ болон өөр 2 бүхэл тоо $r_{e}$ and $c_{e}$ $(1 ≤ r_{e} ≤ m, 1 ≤ c_{e} ≤ n)$ өгөгдөнө. Эдгээр нь онцгой зам нь $(r_{s}, c_{s})$ блокоос эхлэн $s$ тэмдэгт мөр доторх дарааллаар замын уулзваруудыг өнгөрөн явж $(r_{e}, c_{e})$ блок дээр дуусахыг илэрхийлэх юм. $s$-ын урт нь $1$ болон $1000$-ын хооронд байна

Тэмдэгт мөр $s$ нь эхлэлийн байрлалаас төгсгөлийн байрлал хүртэлх зөв замыг тэмдэглэсэн байх ба уг тэмдэгт мөрийн ямар ч дараалсан 2 үсэг нь ижилхэн байхгүй. Мөн эхлэлийн байрлал $(r_{s}, c_{s})$ болон төгсгөлийн байрлал $(r_{e}, c_{e})$ нь гудамжны блокууд байна.

Гаралт

Дан мөрөнд яг $k$ минутын дараах хөгшин Пэйкан-ын байрлалыг илэрхийлэх 2 бүхэл тоо $r_{f}$ болон $c_{f}$-г хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3 10 12
##########
#z1a1111b#
##########
2 3 ab 2 8
Гаралт
2 8
Оролт
10 3 5
###
#w#
#1#
#a#
#1#
#1#
#1#
#1#
#b#
###
3 2 abababababababab 6 2
Гаралт
8 2
Оролт
3 10 6
##########
#z1a1311b#
##########
2 3 ab 2 8
Гаралт
2 7
Сэтгэгдлүүдийг ачааллаж байна...