G. Буудлагын саравч

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

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

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

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

Берланд-ын тоглоомын парк-д байрлах буудлагын саравч нь дэлхийн нэгэн шилдэг буудлагын саравч билээ. Өдөр болгон улсын шилдэг буудагчид уг газар ирж өөрсдийн чадвараа хөгжүүлэх бөгөөд маш олон тооны үйлчлүүлэгчид том шагналыг хожихын тулд шавар тагтаануудыг буудаж өрсөлддөг байжээ. Уг парк-ын удирдлагууд саяхнаас уг буудлагын саравчны онлайн хувилбарыг бүтээхээр шийджээ. Маш хичээнгүй зүтгэлийн явцад уг ажлыг бүтээхийн тулд буудах үйл явцыг хуулбарлах программ хэрэгтэй болсон байв. Уг программын шаардлагыг боловсруулахын тулд буудлагын саравчийг албан ёсоор дүрслэх хэрэгтэй болов. 3D Декартын координатын систем өгөгдөв. Энд $X$ тэнхлэг нь буудагчийн байрлаж буй шулууны дагуу, буудлагын саравчны шалтай хөндлөнгөөр хөдлөх ба $Y$ тэнхлэг нь саравчны хананы дагуу босоо чиглэлд хөдлөх бөгөөд $Z$ тэнхлэгийн эерэг чиглэл нь буудлагыг чиглэлтэй харгалзаж байх юм. $XOY$ хавтгайг буудлагын хавтгай гэж нэрлэх ба уг хавтгайн ямар нэгэн цэгүүд дээрээс бүх сумнууд нь бууны амнаас гарна гэж үзэх бөгөөд сумнууд нь $Z$ тэнхлэгтэй параллель байдлаар нисэх юм. Шавар тагтаа болгон нь талууд нь $X$ болон $Y$ тэнхлэгтэй параллель байх тэгш өнцөгтөөр дүрслэгдэх бөгөөд уг тагтаанууд нь эерэг $z$ координаттай байна. Бай бүрийн хувьд шавар тагтаа болон буудлагын хавтгай 2-ын хоорондох зай үргэлж ялгаатай байх бөгөөд хэрэв сум нь тэгш өнцөгтийн ирмэг эсвэл дотор хэсгээр нэвт гарч байвал уг байг сум оносон байна гэж үзэх юм. Сум байг онох үед бай нь буудлагын саравчны шалны доошоо босоо байдлаар унах бөгөөд дахин уг бай уруу буудах боломжгүй болох юм.

Байнууд нь маш нягт учраас сум нь байг нэвт гарч чадахгүй бөгөөд хэрэв сум нь байг оносон бол цааш нисэн явж чадахгүй болох юм. Оролтын өгөгдөл өгөх программ нь бүх байнуудын байршил болон бүх буудалтуудын байршлуудыг буудалт хийсэн дарааллынх нь дагуу өгөх юм. Программ нь аль бай нь аль буудалтаар оногдсон болохыг тодорхойлох ёстой байв. Хэрэв та хараахан анзаараагүй байгаа бол та уг программыг бичих нэгэн юм!

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) өгөгдөх ба энэ нь нийт байн тоог илэрхийлнэ. Дараагийн $n$ мөрийн мөр болгонд нэг ширхэг байн тайлбар өгөгдөнө. Бай нь $x_{l}, x_{r}, y_{l}, y_{r}, z$ гэсэн 5-н ширхэг бүхэл тоогоор дүрслэгдэх бөгөөд эдгээр нь уг байн огторгуйн байрлалыг ($0 ≤ x_{l} < x_{r} ≤ 10^{7}, 0 ≤ y_{l} < y_{r} ≤ 10^{7}, 0 < z ≤ 10^{7}$) дүрсэлнэ. Дараагийн мөрөнд бүхэл тоо $m$ ($1 ≤ m ≤ 10^{5}$) өгөгдөх ба энэ нь нийт хийх буудалтын тоог илэрхийлнэ. Дараа нь $m$ ширхэг мөрөнд буудалтуудыг дүрсэлнэ. Буудалт болгон нь буудлагын хавтгай дээр байх сумны координатууд $(x, y)$ ($0 ≤ x, y ≤ 10^{7}$, сумнуудын координатууд нь бүхэл тоонууд байна)-аар дүрслэгдэх юм. Буудалтуудыг оролтод өгөхдөө буудалт хийсэн дарааллын дагуу өгсөн байна. Буудалтуудын хоорондох интервал нь хангалттай том байх бөгөөд байнууд нь маш хурдан доош унана гэж үзэх юм. Ийм учраас ямар нэгэн буудалт хийж байг оносны дараа уг оногдсон бай нь дараагийн буудалтад саад учруулахгүй гэж үзнэ үү.

Гаралт

Буудалт бүрийн хувьд уг буудалтын оносон байн дугаарыг эсвэл хэрэв уг сум нь ямар ч бай оноогүй бол 0-ыг дан мөрөнд хэвлэнэ үү. Байнууд нь оролтод өгөгдсөн дарааллынхаа дагуу 1-ээс эхлэн дугаарлагдсан байна.

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

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

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