D. Тесиүс болон төөрдөг байшин

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

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

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

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

Тесиүс Крэт хотод ирмэгцээ л Майнотаур-тай тулалдахаар болжээ. Тэрээр $1 × 1$ хэмжээ бүхий блокуудаас тогтох $n × m$ хэмжээтэй тэгш өнцөгтөн хэлбэртэй төөрдөг байшин олжээ.

Уг төөрдөг байшингийн блок болгон нь нэг товчлууртай бөгөөд уг товчлуур нь бүх блокуудыг цагийн зүүний дагуу $90$ градус эргүүлдэг байв. Блок болгон нь өөрийнхөө төвийг тойрч эргэх бөгөөд уг төөрдөг байшин доторх өөрийн байрлалаа солихгүйгээр зөвхөн төвөө тойрч эргэдэг. Түүнчлэн блок болгон нь хэсэг тооны хаалганууд агуулж байв (ямар ч хаалгагүй байх боломжтой). Нэг минутад Тесиүс бүх блокуудыг цагийн зүүний дагуу $90$ градус эргүүлэхийн тулд ямар нэгэн товчлуурыг дарна эсвэл зүгээр л хөрш блок уруу явна. Хэрэв $A$ блок нь $B$ блок уруу хүргэх хаалгатай бөгөөд $B$ блок нь $A$ блок уруу хүргэх хаалгатай байвал Тесиүс $A$ блокоос хөрш блок болох $B$ блок уруу явж чадах юм.

Тесиүс төөрдөг байшин уруу орох хаалгыг олсон ба одоо тэрээр $(x_{T}, y_{T})$ блок буюу $x_{T}$ мөр болон $y_{T}$ баганад байрлах блок дээр байрлаж байв. Тесиүс $(x_{M}, y_{M})$ блок дотор Майнотаур нуугдаж байгааг мэдэж байгаа бөгөөд тус блок уруу очихын тулд хамгийн цөөн тооны минут зарцуулахыг хүсжээ.

Тесиүс нь эрэлхэг баатар бөгөөд программист биш билээ. Тиймээс таны тусламжийг хүсжээ.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 1000$) өгөгдөх ба эдгээр нь харгалзан төөрдөг байшингийн мөр болон баганын тоог илэрхийлнэ.

Дараагийн $n$ мөрийн мөр болгонд $m$ ширхэг тэмдэгт өгөгдөх ба эдгээр нь төөрдөг байшингийн блокуудыг илэрхийлнэ. Доор эдгээр тэмдэгтүүдийг дүрслэв:

  • «$+$» гэсэн тэмдэгт нь уг блок $4$ хаалгатай болохыг илэрхийлнэ (хөрш блок болгон уруу хүргэх нэг хаалга);
  • «$-$» гэсэн тэмдэгт нь уг блок $2$ хаалгатай болохыг илэрхийлнэ -- зүүн болон баруун талын хөрш блок уруу хүргэх хаалганууд;
  • «$|$» гэсэн тэмдэгт нь уг блок $2$ хаалгатай болохыг илэрхийлнэ -- дээд болон доод талын хөрш блок уруу хүргэх хаалганууд;
  • «$^$» гэсэн тэмдэгт нь уг блок $1$ хаалгатай болохыг илэрхийлнэ -- дээд талын хөрш уруу хүргэх хаалга;
  • «$>$» гэсэн тэмдэгт нь уг блок $1$ хаалгатай болохыг илэрхийлнэ -- баруун талын хөрш уруу хүргэх хаалга;
  • «$<$» гэсэн тэмдэгт нь уг блок $1$ хаалгатай болохыг илэрхийлнэ -- зүүн талын хөрш уруу хүргэх хаалга;
  • «$v$» гэсэн тэмдэгт нь уг блок $1$ хаалгатай болохыг илэрхийлнэ -- доод талын хөрш уруу хүргэх хаалга;
  • «$L$» гэсэн тэмдэгт нь уг блок $3$ хаалгатай болохыг илэрхийлнэ -- зүүн талын хөршөөс бусад бүх хөрш уруу хүргэх хаалганууд;
  • «$R$» гэсэн тэмдэгт нь уг блок $3$ хаалгатай болохыг илэрхийлнэ -- баруун талын хөршөөс бусад бүх хөрш уруу хүргэх хаалганууд;
  • «$U$» гэсэн тэмдэгт нь уг блок $3$ хаалгатай болохыг илэрхийлнэ -- дээд талын хөршөөс бусад бүх хөрш уруу хүргэх хаалганууд;
  • «$D$» гэсэн тэмдэгт нь уг блок $3$ хаалгатай болохыг илэрхийлнэ -- доод талын хөршөөс бусад бүх хөрш уруу хүргэх хаалганууд;
  • «$*$» гэсэн тэмдэгт нь уг блок ямар ч хаалгагүй болохыг илэрхийлнэ.

Зүүн, баруун, дээд болон доод гэсэн чиглэлүүд нь төөрдөг байшинг хүснэгт гэж авж үзэн тодорхойлсон чиглэлүүд бөгөөд уг хүснэгтийн мөрүүд нь дээрээсээ доош хүртэл $1$-ээс $n$ хүртэл дугаарлагдсан ба баганууд нь зүүнээсээ баруун хүртэл $1$-ээс $m$ хүртэл дугаарлагдсан байна.

Дараагийн мөрөнд 2 бүхэл тоо өгөгдөх ба энэ нь Тесиүс-ын анх байрлаж буй блокийн координатууд буюу $(x_{T}, y_{T})$ ($1 ≤ x_{T} ≤ n$, $1 ≤ y_{T} ≤ m$)-ыг илэрхийлнэ.

Сүүлийн мөрөнд Майнотаур-ын нуугдаж буй блокийн координатууд буюу $(x_{M}, y_{M})$ ($1 ≤ x_{M} ≤ n$, $1 ≤ y_{M} ≤ m$)-ыг илэрхийлэх 2 бүхэл тоо өгөгдөнө.

Мөн Тесиүс-ын анх байрлаж буй блок болон Майнотаур-ын нуугдаж буй блокууд нь дор хаяж заавал нэг хаалгатай байна. Тесиүс болон Майнотаур анхандаа нэг ижил блок дээр байрласан байж болох юм.

Гаралт

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

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

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

Оролт
2 2
+*
*U
1 1
2 2
Гаралт
-1
Оролт
2 3
<><
><>
1 1
2 1
Гаралт
4

Тэмдэглэл

Тесиүс-ыг $(x_{T}, y_{T})$ блокоос хөдлөхөд хугацаа нь $0$ гэсэн моментоос эхэлнэ гэж тооцно уу.

Сэтгэгдлүүдийг ачааллаж байна...