C. Ноёны зам

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

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

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

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

$10^{9}$ мөр ба $10^{9}$ баганатай шатрын хөлөг дээр хар ноён зогсож байна. Бид мөрүүдийг дээрээсээ доошоо $1$-c $10^{9}$ хүртэл бүхэл тоогоор дугаарлагдсан гэж үзнэ. Үүнтэй адилаар багануудыг зүүнээсээ баруун тийш $1$-c $10^{9}$ хүртэл бүхэл тоогоор дугаарлагдсан гэж үзнэ. Мөн бид хөлгийн $i$-р мөр $j$-р баганад байрлах нүдийг $(i, j)$ гэж тэмдэглэнэ.

Өгөгдсөн шатрын хөлгийн зарим нүднүүд зөвшөөрөгдсөн гэдгийг та мэдэж байна. Шатрын хөлгийн бүх зөвшөөрөгдсөн нүднүүд нь $n$ сегмент хэлбэрээр өгөгдөнө. Сегмент бүр $r_{i}, a_{i}, b_{i}$ $(a_{i} ≤ b_{i})$ гурван бүхэл тоогоор тодорхойлогдох ба $r_{i}$-р мөрийн $a_{i}$ дугаартай баганаас $b_{i}$ дугаартай багана (эдгээр багана өөрсдөө орно) хүртэлх бүх нүд зөвшөөрөгдсөн гэдгийг заана.

Таны ажил бол ноёны $(x_{0}, y_{0})$ нүднээс $(x_{1}, y_{1})$ нүд хүрэхэд шаардлагатай нүүдлүүдийн хамгийн бага тоог олох юм. Ноён зөвхөн зөвшөөрөгдсөн нүднүүдийн дагуу л нүүнэ. Өөрөөр хэлбэл ноён нүүх замдаа зөвхөн зөвшөөрөгдсөн нүдэнд л байрлаж болно.

Мэдээж шатрын ноён нэг нүүдэлдээ дурын хөрш нүдрүү нүүж чадна. Ядаж нэг цэгээрээ холбогдсон хоёр нүдийг хөрш нүднүүд гэнэ.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан дөрвөн бүхэл тоо $x_{0}, y_{0}, x_{1}, y_{1}$ $(1 ≤ x_{0}, y_{0}, x_{1}, y_{1} ≤ 10^{9})$ байх буюу ноёны анхны болон эцсийн байрлал юм.

Хоёр дахь мөрөнд нэг бүхэл тоо $n$ $(1 ≤ n ≤ 10^{5})$ байх ба зөвшөөрөгдсөн нүднүүдийн сегментүүдийн тоо байна. $i$-р мөрөнд зайгаар тусгаарласан гурван бүхэл тоо $r_{i}, a_{i}, b_{i}$ $(1 ≤ r_{i}, a_{i}, b_{i} ≤ 10^{9}, a_{i} ≤ b_{i})$ байх ба $i$-р сегментийн тодорхойлолт байна. Зөвшөөрөгдсөн нүднүүдийн сегментүүд хоорондоо огтлолцож болно.

Ноёны анхны болон эцсийн байрлалууд зөвшөөрөгдсөн нүднүүд байна. Ноёны анхны болон эцсийн байрлалууд хоорондоо давхцахгүй. Өгөгдсөн бүх сегментийн нийт урт $10^{5}$-с хэтрэхгүй.

Гаралт

Хэрвээ анхны болон эцсийн байрлалын хооронд зөвшөөрөгдсөн нүднүүдээс бүрдсэн зам олдохгүй бол -1-г хэвлэ.

Бусад тохиолдолд ноён эхний байрлалаас эцсийн байрлал хүрэхэд шаардлагатай үйлдлүүдийн хамгийн бага тоог илэрхийлэх нэг бүхэл тоо хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
5 7 6 11
3
5 3 8
6 7 11
5 2 5
Гаралт
4
Оролт
3 4 3 10
3
3 1 4
4 5 9
3 10 10
Гаралт
6
Оролт
1 1 2 10
2
1 1 3
2 6 10
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...