D. Жуулчид

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

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

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

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

Ултима Түл хотын цэцэрлэгт байх 2 жуулчны алхах маршрут нь дараах зарчмын дагуу үргэлжилнэ:

  • Бид Картесианын координатын системийг ашиглана.
  • Хугацааны ямар нэгэн заалт дээр 2 жуулчин $( - 1, 0)$ цэгээс болон $(1, 0)$ цэгээс нэгэн зэрэг алхана. Эхний жуулчин $( - 1, 0)$-ээс алхах ба 2-дахь жуулчин нь $(1, 0)$-ээс алхана.
  • Жуулчид нь хосоороо ижилхэн $1$ (секундэд алхах зайны нэгж) гэсэн хурдаар алхах ба эхний жуулчин нь $x =  - 1$ шулууны дагуу, 2-дахь жуулчин нь $x = 1$ шулууны дагуу алхах юм. Жуулчид $Oy$ тэнхлэг дагуух эерэг чиглэл уруу алхана.
  • Хугацааны ямар нэгэн заалт дээр хананууд гарч ирнэ. $(l_{i}, r_{i})$ хана нь $(0, l_{i})$ болон $(0, r_{i})$ цэгүүдийн хоорондох хэрчим байна. Хана бүр нь маш хурдан гарч ирэх юм.

Ултима Түл-ийн засгийн газар нэгэн зэрэг алхах хос жуулчид бүрийн хувьд дараах зүйлийг мэдэхийг хүсжээ: Тэдгээр жуулчид хэр удаан (секундээр) нэг нэгнээ харахгүй байх вэ? Хэрэв хавтгай дээрх тэдгээрийн байрлалыг холбох хэрчим нь дор хаяж нэг ширхэг ханатай огтлолцож байвал тэдгээр 2 жуулчдыг нэг нэгнээ харахгүй байна гэж үзнэ. Хэрэв 2 хэрчим нь дор хаяж нэг ширхэг ерөнхий цэгтэй байвал эдгээр 2 хэрчмийг огтлолцож байна гэж үзнэ. Бид хэрчмийн төгсгөлүүд нь уг хэрчимдээ харьяалагдана гэж үзнэ.

Засгийн газарт туслан шаардлагатай хугацааг тооцоолж өгнө үү. Хананууд нь огтлолцож (ямар ч байдлаар) эсвэл давхцаж болохыг анхаарна уу.

Оролт

Эхний мөрөнд хос жуулчдын тоо болон баригдсан ханануудын тоог илэрхийлэх зайгаас тусгаарлагдсан 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 10^{5}$) өгөгдөнө. Дараагийн $m$ мөрийн мөр болгонд зайгаар тусгаарлагдсан 3 бүхэл тоо $l_{i}$, $r_{i}$ болон $t_{i}$ ($0 ≤ l_{i} < r_{i} ≤ 10^{9}$, $0 ≤ t_{i} ≤ 10^{9}$) өгөгдөх ба эдгээр нь ханануудын төгсгөлүүд болон уг хана гарч ирэх хугацааны заалтыг илэрхийлнэ. Сүүлийн мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан ялгаатай эрс өсөх бүхэл тоонууд $q_{1}, q_{2}, ..., q_{n}$ ($0 ≤ q_{i} ≤ 10^{9}$) өгөгдөх ба эдгээр нь хос жуулчдын алхаж эхлэх үеийн хугацааны заалтыг илэрхийлнэ.

Бүх цагийн заалтууд нь секундээр өгөгдөнө.

Гаралт

Хос жуулчид бүрийн хувьд дан мөрөнд эдгээр жуулчид нэг нэгнээ харахгүй байх хугацааг секундээр илэрхийлэх ганц бүхэл тоог хэвлэнэ. Эдгээр тоонуудыг жуулчид нь оролтод өгөгдсөн дарааллаар хэвлэнэ үү

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

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

Оролт
2 2
1 4 3
3 6 5
0 1
Гаралт
2
4
Оролт
3 3
0 3 4
0 1 2
2 4 0
1 3 4
Гаралт
2
4
4
Сэтгэгдлүүдийг ачааллаж байна...